Universal Cup Judging System

Universal Cup

حد الوقت: 1.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Dato un albero non radicato con $n$ nodi, devi assegnare un peso distinto a ciascun nodo, con i pesi che formano una permutazione dei numeri da $1$ a $n$.

Per qualsiasi schema di assegnazione, consideriamo tutti i diametri dell'albero (cioè il cammino semplice più lungo nell'albero). Tra questi diametri, selezioniamo quello con la sequenza di pesi lessicograficamente più grande (disponendo i pesi dei nodi lungo il cammino in ordine e confrontandoli lessicograficamente).

Il tuo obiettivo è minimizzare l'ordine lessicografico della sequenza di pesi corrispondente a questo "diametro lessicograficamente più grande" tra tutti i possibili schemi di assegnazione.

Input

Un singolo caso di test contiene più gruppi di dati.

La prima riga dell'input è il numero di gruppi di dati $T$ ($1 \le T \le 10^5$), che rappresenta il numero di gruppi di dati in questo caso di test.

Per ogni gruppo di dati, la prima riga contiene un intero $n$ ($2 \le n \le 2 \cdot 10^5$) che indica il numero di nodi.

Le successive $n - 1$ righe contengono ciascuna due interi $u, v$ ($1 \le u, v \le n$), che rappresentano un arco dell'albero.

È garantito che, considerando tutti i dati, $\sum n \le 2 \cdot 10^5$.

Output

Per ogni set di dati, stampa una riga di diversi interi che rappresentano il più piccolo ordine lessicografico possibile del diametro con il più grande ordine lessicografico.

Esempio

Input

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

Output

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.