Codeforces Round 698 (Div. 1) |
---|
Закончено |
Nezzar придумал абсолютно новую игру «Тайные перестановки» и собирается сыграть в нее со своим лучшим другом Nanako.
В начале игры Nanako и Nezzar оба знают два целых числа $$$n$$$ и $$$m$$$. Игра происходит следующим образом.
Однако 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:
Поскольку Nezzar не проиграл моментально, Nezzar получает счет $$$4$$$, потому что $$$p_i \neq q_i$$$ для всех $$$1 \leq i \leq 4$$$. Очевидно, что это максимально возможный счет, который Nezzar может получить.
Название |
---|