Вам задан полный ориентированный граф \(K_n\) из \(n\) вершин: у каждой пары вершин \(u \neq v\) в \(K_n\) есть обе дуги \((u, v)\) и \((v, u)\); петель в графе нет.
Вам нужно найти такой цикл в \(K_n\), который проходит по каждой дуге ровно один раз (вершины можно посещать несколько раз).
Мы можем выписать такой цикл как список из \(n(n - 1) + 1\) вершин \(v_1, v_2, v_3, \dots, v_{n(n - 1) - 1}, v_{n(n - 1)}, v_{n(n - 1) + 1} = v_1\) — порядок обхода, в котором каждая дуга \((v_i, v_{i + 1})\) встречается по одному разу.
Найдите лексикографически минимальный такой цикл. Не трудно доказать, что такой цикл всегда существует.
Так как ответ может быть слишком большим, выведите только его \([l, r]\) отрезок, то есть \(v_l, v_{l + 1}, \dots, v_r\).
Выходные данные
Для каждого набора входных данных выведите отрезок \(v_l, v_{l + 1}, \dots, v_r\) лексикографически минимального цикла, который проходит по каждой дуге ровно один раз.
Примечание
Во втором наборе, лексикографически минимальный цикл выглядит следующим образом: \(1, 2, 1, 3, 2, 3, 1\).
В третьем примере, довольно очевидно, что цикл должен начинаться и заканчиваться в вершине \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 1 3
3 3 6
99995 9998900031 9998900031
|
1 2 1
1 3 2 3
1
|