F. 分组划分

每个测试点时间限制：1 秒
内存限制：256 兆字节

在第 31 中学，有两组奥林匹克参赛者：计算机科学组和数学组。计算机科学组的人数为 $n_1$，数学组的人数为 $n_2$。目前尚不清楚谁属于哪个组，但已知某些人之间存在友好关系（这些关系可能存在于同组或不同组的人之间）。

这些关系非常牢固，以至于即使移除一个人及其所有友好关系，任意两个人仍然能够通过直接或间接的朋友相互认识。

† 形式化定义：两个人 $(x, y)$ 相识，当存在若干人 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n_1 + n_2$）同时满足以下条件：

• 人 $x$ 与 $a_1$ 直接相识；
• 人 $a_n$ 与 $y$ 直接相识；
• 对任意 $1 \le i \le n-1$，人 $a_i$ 与 $a_{i+1}$ 直接相识。

老师们对计算机科学家与数学家之间交朋友的现象感到不满，因此他们决定将学生重新划分为两个组，使得以下两个条件成立：

• 计算机科学组恰好有 $n_1$ 人，数学组恰好有 $n_2$ 人。
• 任意两名计算机科学家应该相互认识（允许通过同组的朋友间接认识），同样地，任意两名数学家也应该相互认识。

请帮助他们解决这个问题，并找出谁属于哪个组。

输入
每个测试包含多个测试用例。第一行一个整数 $t$（$1 \le t \le 1000$）——测试用例个数。接下来是每个测试用例的描述。

每个测试用例的第一行包含三个整数 $n_1, n_2, m$（$1 \le n_1, n_2 \le 2000$，$1 \le m \le 5000$）。$n_1, n_2$ 是题目中描述的两个组的大小，$m$ 是初始友好关系的数量。

接下来 $m$ 行，每行描述一条友好关系：第 $i$ 行给出一个数对 $(a, b)$，表示编号为 $a$ 的人与编号为 $b$ 的人互相是朋友。

保证每个测试用例中所有友好关系互不相同。

保证所有测试用例的 $n_1 + n_2$ 之和不超过 $2000$，且 $m$ 之和不超过 $5000$。

同时保证每个测试用例的解存在。

如果有多个答案，输出任意一个。

输出
对于每个测试用例，输出两行。
第一行输出 $n_1$ 个互不相同的数字 $a_i$（$1 \le a_i \le n_1 + n_2$）——属于第一组的人。
第二行输出 $n_2$ 个互不相同的数字 $b_i$（$1 \le b_i \le n_1 + n_2$）——属于第二组的人。
所有数字必须互不相同。

如果有多个可能的答案，输出任意一个。

示例
输入

3
1 2 3
2 3
1 3
1 2
1 4 7
2 5
3 4
2 4
1 2
3 5
4 5
1 5
3 3 7
1 2
1 6
2 3
2 5
3 4
4 5
4 6

输出

3 
1 2 
5 
1 2 3 4 
4 5 6 
1 2 3 

说明
考虑第三个测试用例。分组情况如下图所示：
被选为计算机科学家的人用绿色标记，被选为数学家的人用蓝色标记。

考虑所有计算机科学家对：

• 对 $(4,5)$、$(4,6)$ 直接相识。
• 对 $(5,6)$ 通过计算机科学家 $4$ 间接相识。

考虑所有数学家对：

• 对 $(1,2)$、$(2,3)$ 直接相识。
• 对 $(1,3)$ 通过数学家 $2$ 间接相识。

因此，任意一对同组的人均相互认识，该分组正确。