CF1477D Nezzar and Hidden Permutations

Nezzar 设计了一种新游戏“隐藏的排列”，并将其分享给了他最好的朋友 Nanako。 游戏开始时，Nanako 和 Nezzar 都知道两个整数 $n,m$ 的值。游戏将以如下方式进行： - 首先，Nezzar 隐藏两个 $1$ 到 $n$ 的整数排列 $p_1,p_2,\cdots,p_n$ 和 $q_1,q_2,\cdots,q_n$，同时 Nanako 秘密地选择 $m$ 个无序数对 $(l_1,r_1),(l_2,r_2),\cdots,(l_m,r_m)$； - 之后，Nanako 告诉 Nezzar 自己选择的数对； - 收到这 $m$ 个无序数对后，Nezzar 检查是否存在 $1\le i\le m$，使得 $(p_{l_i}-p_{r_i})$ 和 $(q_{l_i}-q_{r_i})$ 的正负号不同。如果存在，Nezzar 获得 $-1$ 分并立即输掉游戏。否则，Nezzar 获得的分数是满足 $p_i\ne q_i$ 的下标 $1\le i\le n$ 的个数。 然而，Nezzar 意外得知了 Nanako 选择的无序数对并打算以此获利。请帮助 Nezzar 找出两个排列 $p,q$ 使得他的得分最大。

多组数据。第一行一个整数 $t(1\le t\le 5\times 10^5)$，表示数据组数。 对于每组数据，第一行两个整数 $n,m(1\le n\le5\times 10^5,0\le m\le \min(\frac{n(n-1)}{2},5\times 10^5))$。 接下来 $m$ 行，每行两个整数 $l_i,r_i(1\le l_i,r_i\le n,l_i\ne r_i)$，表示 Nanako 选择的第 $i$ 个无序数对。保证 $m$ 个无序数对互不相同。 保证单个测试点内 $n$ 的和与 $m$ 的和均不超过 $5\times 10 ^5$。

对于每组数据，输出两行，第一行 $n$ 个整数 $p_1,p_2,\cdots,p_n$，第二行 $n$ 个整数 $q_1,q_2,\cdots,q_n$，使得 Nezzar 的得分最大。

**样例解释** 对于第一组数据，考虑 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 不会立即输掉游戏并获得 $4$ 分，因为对于所有 $1\le i\le 4$，$p_i\ne q_i$ 均成立。很明显这是 Nezzar 能获得的最高分。