鸽子分配编号

题目背景

你面前有一棵树，这棵树共有 \(n\) 个结点，结点之间由 \(n-1\) 条树枝相连，并且每个结点上都放着一只鸽子。现在你需要对这些鸽子进行编号，设第 \(i\) 只鸽子的编号为 \(p_i\)。你需要满足以下条件：

• 序列 \(p\) 为一个 \(1 \sim n\) 的排列，即 \(1 \sim n\) 中的每个数在所有鸽子的编号中恰好出现一次；
• 对于结点 \(u, v\)，若结点 \(u\) 与结点 \(v\) 之间存在一根树枝，则结点 \(u\) 上的鸽子编号与结点 \(v\) 上的鸽子编号之和不大于 \(n+1\)，即 \(p_u + p_v \le n + 1\)。

你需要找到一种符合上述条件的鸽子编号方式。

可以证明，对于每个测试数据，必定存在至少一种合法的编号方式。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 \(T\)，表示测试数据组数。接下来对于每组测试数据：

• 第一行一个整数 \(n\)，表示树的结点数。
• 接下来 \(n-1\) 行，每行包含两个正整数 \(u_i\) 和 \(v_i\)，表示结点 \(u_i\) 与结点 \(v_i\) 之间存在一根树枝。

输出格式

对于每组测试数据，输出一行 \(n\) 个正整数，其中第 \(i\) 个正整数表示你为结点 \(i\) 上的鸽子所分配的编号。

所有满足要求的输出均可通过。

样例

输入

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

输出

1 3 2
1 2 3 4 5

说明

• 样例解释： 对于第 1 组测试数据，结点 \(1\) 上的鸽子编号为 \(1\)，结点 \(2\) 上的鸽子编号为 \(3\)，结点 \(3\) 上的鸽子编号为 \(2\)。由于 \(1+2\) 和 \(1+3\) 都不大于 \(4\)，所以这种编号方式满足条件。

  对于第 2 组测试数据，另一种满足条件的编号方式为：结点 \(1, 2, 3, 4, 5\) 上的鸽子编号分别为 \(2, 1, 4, 5, 3\)。

数据范围

• \(1 \le T \le 10\)；
• \(2 \le n \le 10^5\)；
• \(1 \le u_i, v_i \le n\)；
• 输入数据形成一棵树。

本题采用捆绑测试。

• Subtask 0（21 分）：\(n \le 8\)。
• Subtask 1（25 分）：\(n \le 1000\)。
• Subtask 2（11 分）：对于任意小于 \(n\) 的正整数 \(i\)，都满足 \(u_i = 1\) 且 \(v_i = i + 1\)。
• Subtask 3（18 分）：对于任意小于 \(n\) 的正整数 \(i\)，都满足 \(u_i = i\) 且 \(v_i = i + 1\)。
• Subtask 4（25 分）：无特殊限制。

解法思路

关键观察：

这道题目本质上是给树的每个结点编号，并且要求在树上相邻的结点编号之和不超过 \(n + 1\)。可以通过树的二分性质来解决：

1. 二分图性质：树是二分图，意味着我们可以将树的节点分成两个互不相交的集合，集合间的边都连接着两个不同集合的节点。对于一棵树，我们可以将树按照节点的深度（从根节点开始，深度偶数的节点放一组，深度奇数的节点放另一组）进行二分。

2. 分配编号：假设我们将树分成了两个集合：集合 A 和集合 B。集合 A 中的节点对应着较小的编号，而集合 B 中的节点对应着较大的编号。我们将小集合的编号从 1 开始分配，直到分配完所有编号为止，剩下的编号分配给大集合。

3. 保证条件：由于树的二分性质，任意相邻的结点编号之和一定不会超过 \(n + 1\)。因为相邻的两个结点分别来自集合 A 和集合 B，它们的编号分别较小和较大，和一定小于或等于 \(n + 1\)。

通过这种方法，我们就能很容易地给树的每个节点分配一个满足条件的编号。

总结：

• 二分图性质：树可以分成两部分，分别编号，保证相邻节点的编号之和不会超过最大值。
• 编号策略：根据树的二分结果，给两部分分别编号，并通过合适的顺序分配编号，确保满足条件。