Nezzar 设计了一款全新游戏“隐藏排列”并与他最好的朋友菜菜子分享。
在游戏开始时,Nanako 和 Nezzar 都知道整数 $$$n$$$ 和 $$$m$$$。游戏按照以下方式进行:
- 首先,Nezzar 隐藏了从 $$$1$$$ 到 $$$n$$$ 整数的两个排列 $$$p_1,p_2,\ldots,p_n$$$ 和 $$$q_1,q_2,\ldots,q_n$$$,并且 Nanako 秘密选择 $$$m$$$ 无序对$$$(l_1,r_1),(l_2,r_2),\ldots,(l_m,r_m)$$$;
- 之后,菜菜子将他选择的配对发送给 Nezzar;
- 收到这些 $$$m$$$ 无序对时,Nezzar 检查是否存在 $$$1 \le i \le m$$$,使得 $$$(p_{l_i}-p_{r_i})$$$ 和 $$$(q_{l_i}-q_{r_i})$$$ 具有不同的符号。如果是这样,Nezzar 立即输掉比赛并获得 $$$-1$$$ 分数。否则,Nezzar 获得的分数等于索引数量 $$$1 \le i \le n$$$,使得 $$$p_i \neq q_i$$$。
然而,Nezzar 意外地知道了 Nanako 的无序对并决定利用它们。请帮助 Nezzar 找出两个排列 $$$p$$$ 和 $$$q$$$ 以使分数最大化。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5 \cdot 10^5$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n,m$$$ ($$$1 \le n \le 5 \cdot 10^5, 0 \le m \le \min(\frac{n(n-1)}{2},5 \cdot 10^5)$$$)。
接下来是 $$$m$$$ 行,其中 $$$i$$$ 包含两个整数 $$$l_i,r_i$$$ ($$$1 \le l_i,r_i \le n$$$, $$$l_i \neq r_i$$$),描述 Nanako 选择的第 $$$i$$$ 无序对。保证所有 $$$m$$$ 无序对都是不同的。
保证所有测试用例的$$$n$$$总和不超过$$$5 \cdot 10^5$$$,所有测试用例的$$$m$$$总和不超过$$$5\cdot 10^5$$$。
输出
对于每个测试用例,打印两个排列 $$$p_1,p_2,\ldots,p_n$$$ 和 $$$q_1,q_2,\ldots,q_n$$$ 以使 Nezzar 获得的分数最大化。
示例
输入 #1
3 4 2 1 2 3 4 6 4 1 2 1 3 3 5 3 6 2 1 1 2
输出 #1
1 2 3 4 3 4 1 2 2 3 4 1 6 5 1 4 3 2 5 6 1 2 1 2
注意
对于第一个测试用例,对于 Nanako 给出的每一对:
- 对于第一对 $$$(1,2)$$$:$$$p_1 - p_2 = 1 - 2 = -1$$$, $$$q_1 - q_2 = 3 - 4 = -1$$$,它们具有相同的符号;
- 对于第二对 $$$(3,4)$$$:$$$p_3 - p_4 = 3 - 4 = -1$$$,$$$q_3 - q_4 = 1 - 2 = -1$$$,它们具有相同的符号。
由于 Nezzar 不会立即失败,因此 Nezzar 对于所有 $$$1 \leq i \leq 4$$$ 获得 $$$4$$$ 的分数,即 $$$p_i \neq q_i$$$。显然,这是内扎尔所能得到的最大分数。