#include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node *link;
};
int *displayList(struct node *start);
void displayChef(struct node *start);
struct node *insertInBeginning(struct node *start, int data);
void insertAtEnd(struct node *start, int data);
struct node *deleteNode(struct node *start, int data);
struct node *deleteChef(struct node *start, int data);
int search(struct node *start, int x);
int copyPaste(struct node *start);
int countNodes(struct node *start);
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int n, m, count;
struct node *start = NULL;
scanf("%d%d",&n,&m);
int *a, *b;
a = (int *)malloc((m + 1) * sizeof(int));
for (int i = 1; i <= m; i++)
scanf("%d",&a[i]);
start = insertInBeginning(start, 1);
for (int i = 2; i <= n; i++)
{
insertAtEnd(start, i);
}
for (int i = 1; i <= m; i++)
{
if (search(start, a[i]))
{
start = deleteNode(start, a[i]);
}
}
count=countNodes(start);
int *c;
c=(int*)malloc(count*sizeof(int));
c=displayList(start);
for (int i = 0; i < count; i=i+2)
{
printf("%d ",c[i]);
// cout<<c[i]<<" ";
}
printf("\n");
for (int i = 1; i < count; i=i+2)
{
printf("%d ",c[i]);
}
printf("\n");
}
return 0;
}
struct node *insertInBeginning(struct node *start, int data)
{
struct node *temp;
temp = (struct node *)malloc(sizeof(struct node));
temp->info = data;
temp->link = start;
start = temp;
return start;
}
void insertAtEnd(struct node *start, int data)
{
struct node *temp, *p;
p = start;
while (p->link != NULL)
{
p = p->link;
}
temp = (struct node *)malloc(sizeof(struct node));
temp->info = data;
p->link = temp;
temp->link = NULL;
}
struct node *deleteNode(struct node *start, int x)
{
struct node *temp, *p;
if (start == NULL)
{
printf("List is empty\n");
return start;
}
//Deletion of first node
if (start->info == x)
{
temp = start;
start = start->link;
free(temp);
return start;
}
//Deletion in between or at the end
p = start;
while (p->link != NULL)
{
if (p->link->info == x)
break;
p = p->link;
}
if (p->link == NULL)
printf("Element %d not in list\n\n", x);
else
{
temp = p->link;
p->link = temp->link;
free(temp);
}
return start;
} //End of deleteNode()
int *displayList(struct node *start)
{
struct node *p;
int *b, i = 0;
b=(int *)malloc(100*sizeof(int));
p = start;
while (p != NULL)
{
b[i] = p->info;
i++;
p = p->link;
}
b=(int *)realloc(b, (i+1)*sizeof(int));
return b;
} // End of displayList()
int search(struct node *start, int x)
{
struct node *p;
int position = 1;
p = start;
while (p != NULL)
{
if (p->info == x)
break;
position++;
p = p->link;
}
if (p == NULL)
return 0;
else
return 1;
} //End of search()
int countNodes(struct node *start)
{
int n = 0;
struct node *p = start;
while (p != NULL)
{
n++;
p = p->link;
}
return n;
} //End of countNodes()
