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) \lt f_{v}(x)$ when $x\to\infty$;
• $u \lt 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 \lt 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) \lt f_v(x)$ when $x\to\infty$ is equivalent to the following description: there exists a positive number $N$ such that for all $x \gt N$, $f_u(x) \lt 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).

Input

Each 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$.

Output

For 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 \lt n$, $p_i\prec p_{i+1}$.

Note

In 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) \lt 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 \lt x^2$ when $x\to\infty$, so $f_2(x) \lt f_1(x)$. Similarly, $f_3(x)=f_4(x)=f_5(x) \lt f_2(x) \lt f_1(x)$. Thus, $3\prec 4\prec 5\prec 2\prec 1$.