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.

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$ .

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.

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.