CF1477D.Nezzar and Hidden Permutations

Nezzar designs a brand new game "Hidden Permutations" and shares it with his best friend, Nanako.

At the beginning of the game, Nanako and Nezzar both know integers $n$ and $m$. The game goes in the following way:

• Firstly, Nezzar hides two permutations $p_1,p_2,\ldots,p_n$ and $q_1,q_2,\ldots,q_n$ of integers from $1$ to $n$, and Nanako secretly selects $m$ unordered pairs $(l_1,r_1),(l_2,r_2),\ldots,(l_m,r_m)$;
• After that, Nanako sends his chosen pairs to Nezzar;
• On receiving those $m$ unordered pairs, Nezzar checks if there exists $1 \le i \le m$, such that $(p_{l_i}-p_{r_i})$ and $(q_{l_i}-q_{r_i})$ have different signs. If so, Nezzar instantly loses the game and gets a score of $-1$. Otherwise, the score Nezzar gets is equal to the number of indices $1 \le i \le n$ such that $p_i \neq q_i$.

However, Nezzar accidentally knows Nanako's unordered pairs and decides to take advantage of them. Please help Nezzar find out two permutations $p$ and $q$ such that the score is maximized.

Nezzar 设计了一款全新的游戏“隐藏排列”，并与他最好的朋友 Nanako 一起分享。

游戏开始时，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)$；
• 接着，Nanako 将他所选的这些无序对发送给 Nezzar；
• Nezzar 收到这 $m$ 个无序对后，检查是否存在某个 $1 \le i \le m$，使得 $(p_{l_i}-p_{r_i})$ 与 $(q_{l_i}-q_{r_i})$ 符号不同（即一正一负）。若存在这样的 $i$，则 Nezzar 立即输掉游戏，并得分为 $-1$；否则，Nezzar 的得分等于满足 $p_i \neq q_i$ 的下标 $i$（其中 $1 \le i \le n$）的个数。

然而，Nezzar 不慎提前获知了 Nanako 所选的无序对，并决定利用这一信息。请帮助 Nezzar 找出两个排列 $p$ 和 $q$，使得其得分最大化。

The first line contains a single integer $t$ ($1 \le t \le 5 \cdot 10^5$) — the number of test cases.

The first line of each test case contains two integers $n,m$ ($1 \le n \le 5 \cdot 10^5, 0 \le m \le \min(\frac{n(n-1)}{2},5 \cdot 10^5)$).

Then $m$ lines follow, $i$-th of them contains two integers $l_i,r_i$ ($1 \le l_i,r_i \le n$, $l_i \neq r_i$), describing the $i$-th unordered pair Nanako chooses. It is guaranteed that all $m$ unordered pairs are distinct.

It is guaranteed that the sum of $n$ for all test cases does not exceed $5 \cdot 10^5$, and the sum of $m$ for all test cases does not exceed $5\cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, print two permutations $p_1,p_2,\ldots,p_n$ and $q_1,q_2,\ldots,q_n$ such that the score Nezzar gets is maximized.

对于每个测试用例，输出两个排列 $p_1,p_2,\ldots,p_n$ 和 $q_1,q_2,\ldots,q_n$，使得 Nezzar 得到的分数最大化。

For first test case, for each pair given by Nanako:

• for the first pair $(1,2)$: $p_1 - p_2 = 1 - 2 = -1$, $q_1 - q_2 = 3 - 4 = -1$, they have the same sign;
• for the second pair $(3,4)$: $p_3 - p_4 = 3 - 4 = -1$, $q_3 - q_4 = 1 - 2 = -1$, they have the same sign.

As Nezzar does not lose instantly, Nezzar gains the score of $4$ as $p_i \neq q_i$ for all $1 \leq i \leq 4$. Obviously, it is the maximum possible score Nezzar can get.

对于第一个测试用例，针对 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 并未立即失败，且对所有 $1 \leq i \leq 4$ 均有 $p_i \neq q_i$，Nezzar 获得分数 $4$。显然，这是 Nezzar 能获得的最高可能得分。