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\) такие, что счет игры будет максимальным.
Выходные данные
Для каждого набора входных данных выведите две перестановки \(p_1,p_2,\ldots,p_n\) и \(q_1,q_2,\ldots,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 не проиграл моментально, Nezzar получает счет \(4\), потому что \(p_i \neq q_i\) для всех \(1 \leq i \leq 4\). Очевидно, что это максимально возможный счет, который Nezzar может получить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|