Nezzar and Hidden Permutations
Contest: Codeforces Round 698 (Div. 1)
Difficulty rating: 2800
Tags: constructive algorithms, dfs and similar, graphs

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
3
4 2
1 2
3 4
6 4
1 2
1 3
3 5
3 6
2 1
1 2

Example output:
1 2 3 4
3 4 1 2
2 3 4 1 6 5
1 4 3 2 5 6
1 2
1 2

Editorial:
We can describe the problem in graph theory terms:
We are given a graph $$$G$$$ of $$$n$$$ vertices and $$$m$$$ edge. The $$$i$$$-th edge connects vertices $$$l_i$$$ and $$$r_i$$$. We need to write down two numbers on each vertices, on $$$i$$$-th vertex we write $$$p_i$$$ and $$$q_i$$$ on it, so that:
• $$$p$$$ and $$$q$$$ forms a permutation from $$$1$$$ to $$$n$$$,
• For each edge $$$(u,v)$$$, the relative order between $$$p_u$$$ and $$$p_v$$$ must be the same as between $$$q_u$$$ and $$$q_v$$$.
• We want to maximize the number of vertices $$$u$$$, so that $$$p_u \neq q_u$$$.
We can observe the following:
• For any vertex $$$u$$$ with degree $$$n-1$$$, $$$p_u = q_u$$$.
Proof: For such vertex $$$u$$$, let $$$p_u = k$$$. Then, there are exactly $$$k - 1$$$ neighbors of $$$u$$$ that has its $$$p$$$-number smaller than $$$u$$$. Similarly, let $$$q_u = k'$$$. Then, there are exactly $$$k' - 1$$$ neighbors of $$$u$$$ that has its $$$q$$$-number smaller than $$$u$$$. Since the relative order between $$$u$$$ and its neighbors must be the same across $$$p$$$ and $$$q$$$, $$$k' - 1 = k - 1$$$, which leads to $$$k' = k$$$.
We can assign those numbers with any unused number and delete them from the graph. Now we will consider only vertices with degree $$$< m-1$$$, where $$$m$$$ is the number of remaining vertices. We claim that the maximum number of differing position to be exactly $$$m$$$.
As all vertices have degree $$$< m-1$$$, it is easier to consider the complement graph $$$G'$$$, where $$$(u,v)$$$ in $$$G'$$$ is connected if and only if $$$(u,v)$$$ is not connected in $$$G$$$. Notice that $$$G'$$$ consists of connected components and each vertex has at least one neighbor.
We will focus on a single connected component. Let us find any spanning tree of this particular component. If the spanning tree is astar, Let the center of star be $$$u$$$ and the other vertices be $$$v_1, v_2, \cdots v_k$$$. Then, the following is a valid assignment:
• $$$p_u = 1, q_u = k + 1$$$
• $$$p_{v_i} = i + 1, q_{v_i} = i$$$ for $$$1 \leq i \leq k$$$
Otherwise, we claim that we can decompose any tree into different connected stars with at least two nodes each. If we can do so, we can assign numbers $$$1, 2, \cdots k_1$$$ to first star with $$$k_1$$$ nodes, $$$k_1 + 1, k_1 + 2, \cdots k_1 + k_2$$$ to second star with $$$k_2$$$ nodes and so on. Notice that the relative order between nodes of different stars never change.
The remaining part is to decompose tree into stars. There are a lot of algorithms to do so, one of them would be:
• If any neighbors of $$$u$$$ are unassigned, assign $$$u$$$ to be the center of new star component along with all unassigned neighbors of $$$u$$$.
• Otherwise, notice that all neighbors of $$$u$$$ is now a non-center member of some star component. Pick up any of $$$u$$$'s neighbor, $$$v$$$. If the star component of $$$v$$$ has at least two non-center nodes, remove $$$v$$$ from its original star component and make node $$$u$$$ and node $$$v$$$ a star component centered at $$$u$$$. Otherwise, make $$$v$$$ to be the center of its star component and add $$$u$$$ to it.
We can see that the algorithm produces star components of at least two nodes each, and therefore we can apply the assignment of numbers to each stars individually and concat the results. In the end, all nodes will have their $$$p$$$ and $$$q$$$ assigned differently.
It is possible to find all the needed spanning tree in $$$O((n + m) \log n)$$$ time. Then, it takes $$$O(n)$$$ total time to compute answers for all trees. Therefore, time complexity is $$$O((n + m) \log n)$$$.