Universal Cup Judging System

Universal Cup

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

Gegeben ist ein ungewurzelter Baum mit $n$ Knoten. Du musst jedem Knoten ein paarweise verschiedenes Gewicht zuweisen, wobei die Gewichte eine Permutation der Zahlen von $1$ bis $n$ bilden.

Für jedes Zuweisungsschema betrachten wir alle Durchmesser des Baumes (d. h. die längsten einfachen Pfade im Baum). Unter diesen Durchmessern wählen wir denjenigen mit der lexikographisch größten Gewichtsfolge aus (indem wir die Gewichte der Knoten entlang des Pfades der Reihe nach anordnen und lexikographisch vergleichen).

Dein Ziel ist es, die lexikographische Ordnung der Gewichtsfolge, die diesem „lexikographisch größten Durchmesser“ entspricht, über alle möglichen Zuweisungsschemata hinweg zu minimieren.

Eingabe

Ein einzelner Testfall enthält mehrere Datengruppen.

Die erste Zeile der Eingabe ist die Anzahl der Datengruppen $T$ ($1 \le T \le 10^5$), welche die Anzahl der Datengruppen in diesem Testfall darstellt.

Für jede Datengruppe enthält die erste Zeile eine ganze Zahl $n$ ($2 \le n \le 2 \cdot 10^5$), welche die Anzahl der Knoten angibt.

Die nächsten $n - 1$ Zeilen enthalten jeweils zwei ganze Zahlen $u, v$ ($1 \le u, v \le n$), die eine Kante des Baumes darstellen.

Es wird garantiert, dass über alle Daten hinweg $\sum n \le 2 \cdot 10^5$ gilt.

Ausgabe

Gib für jeden Datensatz eine Zeile mit mehreren ganzen Zahlen aus, welche die kleinstmögliche lexikographische Ordnung des Durchmessers mit der größten lexikographischen Ordnung darstellen.

Beispiel

Eingabe

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

Ausgabe

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.