F. To the Infinitytime limit per test2 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output You are given a full binary tree$$$^{\text{∗}}$$$ of $$$n$$$ nodes, rooted at node $$$1$$$. For each node $$$u$$$ ($$$1\le u\le n$$$), we define function $$$f_u : \mathbb R_+ \to \mathbb R_+$$$ as follows: If $$$u$$$ is a leaf$$$^{\text{†}}$$$, then $$$f_u(x)=x$$$; Otherwise, denote the left child of $$$u$$$ as $$$l_u$$$ and the right child of $$$u$$$ as $$$r_u$$$, then $$$f_u(x)=(f_{l_u}(x))^{f_{r_u}(x)}$$$. For two nodes $$$u$$$ and $$$v$$$, we say $$$u\prec v$$$ if and only if one of the following holds: $$$f_{u}(x)<f_{v}(x)$$$ when $$$x\to\infty$$$; $$$u<v$$$, and $$$f_{u}(x)=f_{v}(x)$$$ when $$$x\to\infty$$$$$$^{\text{‡}}$$$. It can be shown that for any two distinct nodes $$$u$$$ and $$$v$$$, either $$$u\prec v$$$ or $$$v\prec u$$$ holds. You have to sort the nodes by order $$$\prec$$$. Formally, you need to find a permutation$$$^{\text{§}}$$$ $$$p$$$ of length $$$n$$$, such that for every $$$1\le i<n$$$, $$$p_i\prec p_{i+1}$$$.$$$^{\text{∗}}$$$A full binary tree is a rooted tree, in which each node has $$$0$$$ or $$$2$$$ children. $$$^{\text{†}}$$$A leaf is any vertex without children. $$$^{\text{‡}}$$$Here, $$$f_u(x) < f_v(x)$$$ when $$$x\to\infty$$$ is equivalent to the following description: there exists a positive number $$$N$$$ such that for all $$$x > N$$$, $$$f_u(x) < f_v(x)$$$ holds. The same is defined for $$$f_u(x) = f_v(x)$$$ when $$$x\to \infty$$$.$$$^{\text{§}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array). InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows. The first line of each test case contains a single integer $$$n$$$ ($$$1\le n \le 4\cdot 10^5$$$, $$$n$$$ is odd) — the size of the full binary tree.Then $$$n$$$ lines follow, the $$$i$$$-th line containing two integers $$$l_i$$$ and $$$r_i$$$ ($$$0\le l_i, r_i\le n$$$) — the left child and the right child of node $$$i$$$. If $$$i$$$ is a leaf, then $$$l_i=r_i=0$$$. It is guaranteed that the given input forms a full binary tree rooted at node $$$1$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$4\cdot 10^5$$$. OutputFor each test case, output $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1\le p_i\le n$$$, all $$$p_i$$$ are distinct) — the permutation you found. You need to guarantee that for each $$$1\le i < n$$$, $$$p_i\prec p_{i+1}$$$.ExampleInput432 30 00 052 34 50 00 00 092 34 50 00 06 78 90 00 00 010 0Output2 3 1
3 4 5 2 1
3 4 7 8 9 6 5 2 1
1
NoteIn the first test case, $$$f_2(x)=f_3(x)=x$$$, and $$$f_1(x)=(f_2(x))^{f_3(x)}=x^x$$$. When $$$x\to\infty$$$, it is clear that $$$f_2(x)=f_3(x)<f_1(x)$$$. Thus, $$$2\prec 3\prec 1$$$.In the second test case, $$$f_3(x)=f_4(x)=f_5(x)=x$$$, $$$f_2(x)=(f_4(x))^{f_5(x)}=x^x$$$, and $$$f_1(x)=(f_2(x))^{f_3(x)}=x^{x^2}$$$. It is clear that $$$x<x^2$$$ when $$$x\to\infty$$$, so $$$f_2(x)<f_1(x)$$$. Similarly, $$$f_3(x)=f_4(x)=f_5(x)<f_2(x)<f_1(x)$$$. Thus, $$$3\prec 4\prec 5\prec 2\prec 1$$$.