题目描述

给一棵 $𝑛$ 个点的二叉树（根节点为 $1$），你可以进行以下操作至多 $1$ 次：

• 选择 $1$ 个（除了根之外的）点 $𝑢$，断开 $𝑢$ 和其父节点之间的边；然后重新选择另一个点作为 $𝑢$ 的父节点、将 $𝑢$ 接上去，需要保证操作之后仍然是一棵以 $1$ 为根的二叉树。

你想要操作之后的二叉树有字典序最小的先序遍历序列，输出这个序列。

输入格式

第一行 $1$ 个整数 $𝑇$，代表有 $𝑇$ 组数据。

每组数据第一行 $1$ 个整数 $𝑛$；接下来 $𝑛$ 行，第 $𝑖$ 行 $2$ 个整数 $𝑙𝑠[𝑖], 𝑟𝑠[𝑖]$ 代表 $𝑖$ 号结点的左右儿子编号，没有左右儿子的话用 $0$ 表示。

输出格式

对于每组数据，输出一行 $𝑛$ 个整数，代表字典序最小的二叉树先序遍历。

12
4
2 3
0 4
0 0
0 0
5
2 3
0 4
0 5
0 0
0 0
6
5 2
3 6
4 0
0 0
0 0
0 0
6
2 3
6 4
0 5
0 0
0 0
0 0
6
5 2
3 0
4 0
6 0
0 0
0 0
6
3 2
4 6
0 0
5 0
0 0
0 0
6
4 2
5 3
0 0
0 0
0 6
0 0
6
3 2
0 0
5 4
0 6
0 0
0 0
6
2 3
0 0
5 4
0 6
0 0
0 0
6
3 2
4 5
0 0
0 6
0 0
0 0
6
2 3
0 4
0 0
0 5
0 6
0 0
6
2 5
3 4
0 0
0 0
6 0
0 0

1 2 3 4
1 2 3 4 5
1 2 3 4 5 6
1 2 4 3 5 6
1 2 3 4 6 5
1 2 4 5 3 6
1 2 5 4 6 3
1 2 3 5 4 6
1 2 3 4 5 6
1 2 4 3 6 5
1 2 3 4 5 6
1 2 3 4 5 6

提示

对于第一个样例，可以把 $3$ 号结点连在 $2$ 号结点的左儿子处。

对于第二个样例，可以把 $4$ 号结点连在 $3$ 号结点的左儿子处 。

数据范围

对于所有数据，令 $\sum n$ 代表每组数据中 $𝑛$ 的和，$1 ≤ 𝑇 ≤ 100,1 ≤ 𝑛 ≤ 10^5, 1 ≤∑𝑛 ≤ 3 × 10^5$，保证输入是一棵以 $1$ 为根的二叉树。

对于测试点 $1\sim 3$：$𝑛 ≤ 10$

对于测试点 $4\sim 8$：$𝑛 ≤ 200$

对于测试点 $9\sim 11$：$𝑛 ≤ 1000$

对于测试点 $12\sim 14$：$𝑛 ≤ 10^5$ 且所有 $𝑙𝑠[𝑖] = 0$

对于测试点 $15$：$𝑛 ≤ 10^5$ 且所有 $𝑟𝑠[𝑖] = 0$

对于测试点 $16\sim 20$：$𝑛 ≤ 10^5$