在$$$31$$$st中学,有两组奥林匹克竞赛参与者:计算机科学和数学。计算机科学家的数量为 $$$n_1$$$,数学家的数量为 $$$n_2$$$。目前尚不清楚谁属于哪个群体,但已知某些人之间存在友好联系(这些联系可能存在于来自同一群体或不同群体的一对人之间)。
这种联系是如此紧密,即使一个人连同他们所有的友好联系都被移除,任何一对人仍然直接或通过共同的朋友相识。
$$$^{\dagger}$$$ 更正式地说,两个人 $$$(x, y)$$$ 在以下情况下是相识的:有个人 $$$a_1, a_2, \ldots,a_n$$$ ($$$1 \le a_i \le n_1 + n_2$$$) ,并且同时满足以下条件:
$$$\bullet$$$ 人 $$$x$$$ 直接认识 $$$a_1$$$。
$$$\bullet$$$ 人 $$$a_n$$$ 直接认识 $$$y$$$。
$$$\bullet$$$ 人 $$$a_i$$$ 直接熟悉 $$$a_{i + 1}$$$ 对于任何 ($$$1 \le i \le n - 1$$$)。
老师们对计算机科学家与数学家是朋友,反之亦然这一事实感到不满,因此他们决定将学生分为两组,并满足以下两个条件:
$$$\bullet$$$ 计算机科学组有 $$$n_1$$$ 人,数学组有 $$$n_2$$$ 人。
$$$\bullet$$$ 任何一对计算机科学家都应该是熟人(允许有共同朋友的熟人,他们必须与一对中的人来自同一组),数学家也应该如此。
帮助他们解决这个问题并找出谁属于哪个组。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$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$$$ ($$$1 \le i \le m$$$) 行中,给出了一对数字 $$$(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$$$) — 属于第二组的人。
所有数字必须不同。
如果有多个可能的答案,请打印任意一个。
示例
输入 #1
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
输出 #1
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$$$ 相识。
我们得出结论,属于同一组的任何一对人都是彼此熟悉的,因此分成两组是正确的。