Eikooc и Sushi играют в игру.
Игра проводится на дереве из \(n\) вершин, пронумерованных от \(1\) до \(n\). Напомним, что дерево с \(n\) вершинами это неориентированный связный граф с \(n-1\) ребрами.
Игроки поочередно перемещают фишку по дереву. Eikooc делает первый ход, помещая фишку на любую вершину по своему выбору. Sushi делает следующий ход, затем Eikooc, затем Sushi, и так далее. В каждый ход после первого, игрок должен переместить фишку в какую-то вершину \(u\) такую, что:
- Между вершинами \(u\) и \(v\) (на которой фишка находится данный момент), есть ребро
- \(u\) не была посещена ранее
- \(u \oplus v \leq min(u, v)\)
Здесь \(x \oplus y\) обозначает операцию побитового исключающего ИЛИ чисел \(x\) и \(y\).
Оба игрока играют оптимально. Игрок, который не может сделать ход, проигрывает.
Ниже приведены примеры, демонстрирующие правила игры.
 Предположим, Eikooc начинает игру, помещая фишку в вершину \(4\). Затем Sushi перемещает фишку в вершину \(6\), которая не была посещена и является соседней к \(4\). Также \(6 \oplus 4 = 2 \leq min(6, 4)\). На следующем ходу Eikooc перемещает фишку в вершину \(5\), которая не была посещена и является соседней к \(6\). Также, \(5 \oplus 6 = 3 \leq min(5, 6)\). У Sushi больше нет ходов для игры, поэтому она проигрывает. |  Предположим, Eikooc начинает игру, помещая фишку в вершинул \(3\). Sushi перемещает фишку в вершину \(2\), которая не была посещена и является соседней к \(3\). Также \(3 \oplus 2 = 1 \leq min(3, 2)\). Eikooc не может переместить фишку в вершину \(6\), так как \(6 \oplus 2 = 4 \nleq min(6, 2)\). Поскольку у Eikooc нет ходов для игры, она проигрывает. |
Перед началом игры Eikooc решает тайком перенумеровать вершины дерева в свою пользу. Формально, перенумерация — это перестановка \(p\) длины \(n\) (последовательность из \(n\) целых чисел, где каждое целое число от \(1\) до \(n\) встречается ровно один раз), где \(p_i\) обозначает новый номер вершины \(i\).
Она хочет максимизировать количество вершин, которые она может выбрать в первый ход, для которых она сможет гарантировать себе победу. Помогите Eikooc найти любую перенумерацию, которая поможет ей в этом.
Выходные данные
Для каждого набора входных данных выведите любую подходящую перестановку — перестановку длины \(n\), которая максимизирует количество вершин, которые Eikooc может выбрать в первый ход и иметь выиграшную стратегию. Если таких перестановок несколько, вы можете вывести любую из них.
Примечание
В первом наборе входных данных у Eikooc есть только одна вершина. У Sushi не будет ходов после того, как Eikooc выберет эту вершину, и Eikooc выиграет.
Во втором наборе входных данных \(1 \oplus 2 = 3 \nleq min(1, 2)\). Следовательно, после того, как Eikooc выберет любую из вершин, у Sushi не останется ходов, и Eikooc выиграет. И \(\{1, 2\}\), и \(\{2, 1\}\) являются допустимыми перенумерациями.