题目描述

称一个 $1 ∼ n$ 的排列 $\{p\} = \{p_1, p_2,\cdots, p_n\}$ 是一棵 $n$ 个点、点编号为 $1$ 至 $n$ 的树 $T$ 的拓扑序列，当且仅当对于任意 $1 ≤ i < n$，恰好存在唯一的 $j > i$ 满足 $p_i$ 与 $p_j$ 之间有连边。

给定树 $T$，你需要给出尽可能少的该树的拓扑序列 $\{p_1\}, \{p_2\}, \cdots, \{p_k\}$，使得有且仅有树 $T$ 满足 $\{p_1\}, \{p_2\}, \cdots, \{p_k\}$ 均为该树的合法拓扑序列。

输入格式

从标准输入读入数据。

本题有多组测试数据。输入第一行一个正整数 $T$，表示测试数据组数，接下来依次输入每组测试数据。

对于每组数据，输入第一行一个正整数 $n$，表示给定树的大小。接下来 $n - 1$ 行，每行两个正整数 $u, v$ 描述树中存在的一条边。

输出格式

输出到标准输出。

对于每组数据，输出第一行一个正整数 $k$ 表示你给出的拓扑序列数量，接下来 $k$ 行，每行输出一个 $1 ∼ n$ 的排列，描述你给出的拓扑序列。你需要保证 $1 ≤ k ≤ n$，且这 $k$ 个拓扑序列均为对应输入的合法拓扑序列，且只有一棵树满足这些拓扑序列都是其合法拓扑序列。

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

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

提示

【子任务】

对于所有测试数据，$1 ≤ T ≤ 100$，$3 ≤ n ≤ 100$，$1 ≤ u, v ≤ n$。

本题共有两个测试点。

特别地，所有测试点中每组数据均为从所有 $n$ 个点的有标号树中等概率随机选择生成得到的。

【评分方式】

对于一个测试点内部的某组数据：

1. 你需要保证 $k$ 以及你输出的序列中每个数都为 $[1, n]$ 范围内的正整数，否则整个测试点将会获得 $0$ 分。

2. 若你给出的序列中存在一个不是输入给定树的拓扑序列，那么你这组数据的得分比例将会是 $0$。

3. 若存在多棵树满足其这些序列都是其合法的拓扑序列，那么你这组数据的得分比例将会是 $0$。

4. 否则如果最优解为 $K$，而你构造的序列数量为 $k$，那么你这组数据的得分比例将为 $0.97^{k-K}$。

一个测试点的得分比例将会是该测试点内所有数据的得分比例的平均值，一个测试点的实际得分值将会是其总分乘以得分比例。