Problem
Asya ama molto gli animali. Recentemente ha acquistato n gattini, ha dato loro identificatori numerici da 1 a n e li ha messi in un recinto. La voliera è una fila di n celle, anch'esse numerate da 1 a n. Le celle vicine sono separate da partizioni a maglie, in totale ci sono n & meno; 1 partizioni nel recinto. Inizialmente, esattamente un gattino con un certo numero sistemato in ogni cella.
Guardando i gattini, Asya ha notato che sono molto amichevoli e alcune coppie di gattini che vivono in celle vicine vogliono davvero giocare tra loro. Per non privarli di questo piacere, Asya iniziò a rimuovere i tramezzi tra celle adiacenti, ingrandendoli.
L'i-esimo giorno, Asya ha fatto quanto segue.
Ho notato che alcuni gattini x
i e y
i, che vivono in celle vicine l'i-esimo giorno, vogliono giocare.
Ho rimosso la partizione tra queste celle, trasformandole in una, in cui sono finiti tutti i gattini delle due celle precedenti.
Poiché Asya non ha restituito i tramezzi, dopo n & meno; 1 giorno il recinto è diventato un'unica cella in cui vivevano tutti i gattini. Essendo molto pedante, Asya ha annotato gli ID del gattino x
i e y
i per ognuno degli n−1 giorni in un diario speciale.
Hai una rivista con queste informazioni, ma non sai come i gattini sono stati sistemati nelle celle in primo luogo. Trova qualsiasi distribuzione di gattini in n celle originali che non contraddica i dati nel registro.
Inserimento
La prima riga contiene un numero intero n (
\(2 \leq n \leq 150000\)) — numero di gattini.
Le successive n−1 righe contengono coppie di numeri interi x
i , y
i (
\(1 \leq x_i , y_i, \leq n,x_i \neq y_i\) ) — identificatori di gattini, tra le celle di cui la partizione è stata rimossa il giorno i. È garantito che i gattini xi e yi non si trovino nella stessa cella a seguito della precedente unione di celle.
Impressum
Stampa n interi distinti p
i (
\(1 \leq p_i \leq n\)), dove p
i – l'identificativo del gattino che originariamente viveva nella cella numero i. Se ci sono più risposte possibili, stampane qualcuna.
Nota
Nella risposta, ad esempio, viene fornito uno dei possibili insediamenti iniziali dei gattini, ci sono altre risposte. L'immagine sotto mostra come le celle sono state unite per questo posizionamento iniziale dei gattini. Tieni presente che con questa disposizione, i gattini che sono diventati amici ogni giorno secondo il diario di Asya si trovano in celle adiacenti.
| Input |
Uscita |
5
14
25
3 1
4 5 |
3 1 4 2 5 |