Universal Cup Judging System

Universal Cup

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

$n$ 頂点の根なし木が与えられます。各頂点に $1$ から $n$ までの順列をなす相異なる重みを割り当てる必要があります。

任意の割り当て方法について、木のすべての直径(すなわち、木内の最長単純パス)を考えます。これらの直径の中から、辞書順で最大の重み列を持つものを選択します(パス上の頂点の重みを順番に並べ、辞書順で比較します)。

あなたの目標は、すべての可能な割り当て方法の中で、この「辞書順最大の直径」に対応する重み列の辞書順を最小化することです。

入力

1 つのテストケースには複数のデータグループが含まれます。

入力の 1 行目はデータグループの数 $T$ ($1 \le T \le 10^5$) であり、このテストケースに含まれるデータグループの数を表します。

各データグループについて、1 行目には頂点数を示す整数 $n$ ($2 \le n \le 2 \cdot 10^5$) が与えられます。

続く $n - 1$ 行には、それぞれ木の辺を表す 2 つの整数 $u, v$ ($1 \le u, v \le n$) が与えられます。

すべてのデータにわたって $\sum n \le 2 \cdot 10^5$ であることが保証されます。

出力

各データセットについて、辞書順最大の直径が取り得る辞書順最小の重み列を表すいくつかの整数を 1 行に出力してください。

入出力例

入力

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.