← 返回题目列表

Codeforces · 1477/D

D. Nezzar 和隐藏排列

中文机器翻译题面 查看原题

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$$$。显然,这是内扎尔所能得到的最大分数。