P11425 [清华集训 2024] 路南柯

称一个 $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$ 个拓扑序列均为对应输入的合法拓扑序列，且只有一棵树满足这些拓扑序列都是其合法拓扑序列。

【子任务】 对于所有测试数据，$1 ≤ T ≤ 100$，$3 ≤ n ≤ 100$，$1 ≤ u, v ≤ n$。 本题共有两个测试点。 | 测试点编号 | 分值 | $T$ | $n$ | | :-: | :-: | :-: | :-: | | $1$ | $20$ | $=10$ | $=10$ | | $2$ | $80$ | $=10^2$ | $=10^2$ | 特别地，所有测试点中每组数据均为从所有 $n$ 个点的有标号树中等概率随机选择生成得到的。 ### 【评分方式】 对于一个测试点内部的某组数据： 1. 你需要保证 $k$ 以及你输出的序列中每个数都为 $[1, n]$ 范围内的正整数，否则**整个测试点**将会获得 $0$ 分。 2. 若你给出的序列中存在一个不是输入给定树的拓扑序列，那么你**这组数据**的得分比例将会是 $0$。 3. 若存在多棵树满足其这些序列都是其合法的拓扑序列，那么你**这组数据**的得分比例将会是 $0$。 4. 否则如果最优解为 $K$，而你构造的序列数量为 $k$，那么你**这组数据**的得分比例将为 $0.97^{k-K}$。 一个测试点的得分比例将会是该测试点内所有数据的得分比例的**平均值**，一个测试点的实际得分值将会是其总分乘以得分比例。