D. Nezzar и тайные перестановки
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Nezzar придумал абсолютно новую игру «Тайные перестановки» и собирается сыграть в нее со своим лучшим другом Nanako.

В начале игры Nanako и Nezzar оба знают два целых числа $$$n$$$ и $$$m$$$. Игра происходит следующим образом.

  • Сначала Nezzar тайно загадывает две перестановки $$$p_1,p_2,\ldots,p_n$$$ и $$$q_1,q_2,\ldots,q_n$$$ целых чисел от $$$1$$$ до $$$n$$$. Nanako тайно загадывает $$$m$$$ неупорядоченных пар $$$(l_1,r_1),(l_2,r_2),\ldots,(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 получает, равен количеству индексов $$$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$$$), описывающих $$$i$$$-ю пару, которую выбрал Nanako. Гарантируется, что все $$$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, будет максимальным.

Пример
Входные данные
3
4 2
1 2
3 4
6 4
1 2
1 3
3 5
3 6
2 1
1 2
Выходные данные
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 получает счет $$$4$$$, потому что $$$p_i \neq q_i$$$ для всех $$$1 \leq i \leq 4$$$. Очевидно, что это максимально возможный счет, который Nezzar может получить.