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