给你一个完整的二叉树$$$^{\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$$$ 对节点进行排序。形式上,您需要找到长度为 $$$n$$$ 的排列$$$^{\text{§}}$$$ $$$p$$$,这样对于每个 $$$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)$$$成立。当 $$$x\to \infty$$$ 时,$$$f_u(x) = f_v(x)$$$ 也有同样的定义。
$$$^{\text{§}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$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}$$$。
示例
输入复制
432 30 00 052 34 50 00 00 092 34 50 00 06 78 90 00 00 010 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\to\infty$$$ 时 $$$x \lt x^2$$$,因此 $$$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$$$。