给定一棵有 $n$ 个节点的满二叉树*，根节点为 $1$。对于每个节点 $u$（$1 \le u \le n$），我们定义函数 $f_u: \mathbb{R}^+ \to \mathbb{R}^+$ 如下：

• 若 $u$ 是叶子节点†，则 $f_u(x) = x$；
• 否则，记 $u$ 的左子节点为 $l_u$，右子节点为 $r_u$，则
  $f_u(x) = \big(f_{l_u}(x)\big)^{f_{r_u}(x)}$。

对于两个节点 $u$ 和 $v$，我们称 $u \prec v$ 当且仅当以下之一成立：

1. 当 $x \to \infty$ 时，$f_u(x) < f_v(x)$；
2. $u < v$，且当 $x \to \infty$ 时，$f_u(x) = f_v(x)$‡。

可以证明，对于任意两个不同的节点 $u$ 和 $v$，要么 $u \prec v$，要么 $v \prec u$ 成立。

你需要按照 $\prec$ 的顺序对节点排序。形式化地说，你需要找到一个长度为 $n$ 的排列§ $p$，使得对于每个 $1 \le i < n$，有 $p_i \prec p_{i+1}$。

输入
每个测试点包含多个测试用例。第一行包含一个整数 $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, \dots, p_n$（$1 \le p_i \le n$，所有 $p_i$ 互不相同），即你找到的排列。需要保证对于每个 $1 \le i < 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) < 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 \to \infty$ 时，$x < x^x$，所以 $f_2(x) < f_1(x)$。类似地，$f_3(x) = f_4(x) = f_5(x) < f_2(x) < f_1(x)$。因此 $3 \prec 4 \prec 5 \prec 2 \prec 1$。

*满二叉树：每个节点要么有 $0$ 个孩子，要么有 $2$ 个孩子的有根树。
†叶子节点：没有孩子的节点。
‡这里，“当 $x \to \infty$ 时 $f_u(x) < f_v(x)$”等价于：存在正数 $N$，使得对所有 $x > N$，$f_u(x) < f_v(x)$ 成立。$f_u(x) = f_v(x)$ 当 $x \to \infty$ 的定义类似。
§长度为 $n$ 的排列：由 $n$ 个互不相同的 $1$ 到 $n$ 的整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 出现两次），$[1,3,4]$ 也不是（$n=3$ 但数组中出现了 $4$）。