Universal Cup Judging System

Universal Cup

Time Limit: 1.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

給定一棵擁有 $n$ 個節點的無根樹,你需要為每個節點分配一個互不相同的權值,這些權值構成一個由 $1$ 到 $n$ 的排列。

對於任意一種分配方案,我們考慮該樹的所有直徑(即樹中最長的簡單路徑)。在這些直徑中,我們選擇字典序最大的權值序列的那條直徑(將沿路徑的節點權值按順序排列並進行字典序比較)。

你的目標是在所有可能的分配方案中,最小化這個「字典序最大的直徑」所對應的權值序列的字典序。

輸入格式

單個測試資料包含多組資料。

輸入的第一行是資料組數 $T$ ($1 \le T \le 10^5$),代表此測試資料中的資料組數。

對於每組資料,第一行包含一個整數 $n$ ($2 \le n \le 2 \cdot 10^5$),代表節點數量。

接下來的 $n - 1$ 行,每行包含兩個整數 $u, v$ ($1 \le u, v \le n$),代表樹的一條邊。

保證在所有資料中,$\sum n \le 2 \cdot 10^5$。

輸出格式

對於每組資料,輸出一行若干個整數,代表具有最大字典序的直徑所能達到的最小可能字典序序列。

範例

輸入

5
5
1 2
1 3
2 4
2 5
4
1 2
1 3
1 4
6
1 2
1 3
2 4
2 5
3 6
8
1 2
2 3
1 4
2 5
3 6
1 7
7 8
10
1 2
2 3
2 4
4 7
4 8
1 5
5 6
6 9
1 10

輸出

3 4 5 1
3 4 2
3 4 5 6 1
2 3 4 5 6 1
3 4 5 6 7 8 1

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.