F. До бесконечности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано полное бинарное дерево$$$^{\text{∗}}$$$ из $$$n$$$ вершин, корень которого находится в вершине $$$1$$$. Для каждой вершины $$$u$$$ ($$$1\le u\le n$$$) мы определяем функцию $$$f_u : \mathbb R_+ \to \mathbb R_+$$$ следующим образом:

  • Если $$$u$$$ является листом$$$^{\text{†}}$$$, то $$$f_u(x)=x$$$;
  • В противном случае, обозначим левого ребёнка $$$u$$$ как $$$l_u$$$, а правого ребёнка $$$u$$$ как $$$r_u$$$, тогда $$$f_u(x)=(f_{l_u}(x))^{f_{r_u}(x)}$$$.

Для двух вершин $$$u$$$ и $$$v$$$ скажем, что $$$u\prec v$$$, если и только если выполняется одно из следующих условий:

  • $$$f_{u}(x) \lt f_{v}(x)$$$ при $$$x\to\infty$$$;
  • $$$u \lt v$$$, и $$$f_{u}(x)=f_{v}(x)$$$ при $$$x\to\infty$$$$$$^{\text{‡}}$$$.

Можно показать, что для любых двух различных вершин $$$u$$$ и $$$v$$$ выполняется либо $$$u\prec v$$$, либо $$$v\prec u$$$.

Вам необходимо отсортировать вершины по порядку $$$\prec$$$. Формально, вам нужно найти перестановку$$$^{\text{§}}$$$ $$$p$$$ длины $$$n$$$, такую что для каждого $$$1\le i \lt n$$$ выполняется $$$p_i\prec p_{i+1}$$$.

$$$^{\text{∗}}$$$Полным бинарным деревом называется корневое дерево, в котором у каждой вершины $$$0$$$ или $$$2$$$ детей.

$$$^{\text{†}}$$$Листом называется любая вершина, у которой нет детей.

$$$^{\text{‡}}$$$Здесь $$$f_u(x) \lt f_v(x)$$$ при $$$x\to\infty$$$ обозначает следующее: существует целое положительное число $$$N$$$, такое что для всех $$$x \gt N$$$ выполняется $$$f_u(x) \lt f_v(x)$$$. Аналогично определяется $$$f_u(x) = f_v(x)$$$ при $$$x\to \infty$$$.

$$$^{\text{§}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n \le 4\cdot 10^5$$$, $$$n$$$ нечетное) — размер полного бинарного дерева.

Затем следуют $$$n$$$ строк, $$$i$$$-я строка содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$0\le l_i, r_i\le n$$$) — левого ребёнка и правого ребёнка вершины $$$i$$$. Если $$$i$$$ является листом, то $$$l_i=r_i=0$$$. Гарантируется, что заданный ввод формирует полное бинарное дерево с корнем в вершине $$$1$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$4\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1\le p_i\le n$$$, все $$$p_i$$$ различны) — перестановку, которую вы нашли. Необходимо, чтобы для каждого $$$1\le i \lt n$$$ выполнялось $$$p_i\prec p_{i+1}$$$.

Пример
Входные данные
4
3
2 3
0 0
0 0
5
2 3
4 5
0 0
0 0
0 0
9
2 3
4 5
0 0
0 0
6 7
8 9
0 0
0 0
0 0
1
0 0
Выходные данные
2 3 1 
3 4 5 2 1 
3 4 7 8 9 6 5 2 1 
1
Примечание

В первом наборе входных данных, $$$f_2(x)=f_3(x)=x$$$, и $$$f_1(x)=(f_2(x))^{f_3(x)}=x^x$$$. Когда $$$x\to\infty$$$, очевидно, что $$$f_2(x)=f_3(x) \lt f_1(x)$$$. Таким образом, $$$2\prec 3\prec 1$$$.

Во втором наборе входных данных, $$$f_3(x)=f_4(x)=f_5(x)=x$$$, $$$f_2(x)=(f_4(x))^{f_5(x)}=x^x$$$, и $$$f_1(x)=(f_2(x))^{f_3(x)}=x^{x^2}$$$. Ясно, что $$$x \lt x^2$$$ при $$$x\to\infty$$$, поэтому $$$f_2(x) \lt f_1(x)$$$. Аналогично, $$$f_3(x)=f_4(x)=f_5(x) \lt f_2(x) \lt f_1(x)$$$. Таким образом, $$$3\prec 4\prec 5\prec 2\prec 1$$$.