Problem
Asya aime beaucoup les animaux. Elle a récemment acheté n chatons, leur a donné des identifiants numériques de 1 à n et les a placés dans un enclos. La volière est une rangée de n cellules, également numérotées de 1 à n. Les cellules voisines sont séparées par des cloisons grillagées, au total il y a n & moins; 1 cloisons dans l'enceinte. Initialement, exactement un chaton avec un certain nombre installé dans chaque cellule.
En observant les chatons, Asya a remarqué qu'ils sont très amicaux et que certains couples de chatons vivant dans des cellules voisines veulent vraiment jouer entre eux. Afin de ne pas les priver de ce plaisir, Asya a commencé à supprimer les cloisons entre les cellules adjacentes, en les agrandissant.
Le ième jour, Asya a fait ce qui suit.
J'ai remarqué que certains chatons x
i et y
i, vivant dans des cellules voisines le ie jour, veulent jouer.
J'ai supprimé la cloison entre ces cellules, les transformant en une seule, dans laquelle se sont retrouvés tous les chatons des deux cellules précédentes.
Comme Asya n'a pas rendu les cloisons, après n'1 jour l'enclos est devenu une seule cellule dans laquelle vivaient tous les chatons. Étant très pédante, Asya a noté les identifiants du chaton x
i et y
i pour chacun des n−1 jours dans un journal spécial.
Vous avez un magazine avec cette information, mais vous ne savez pas comment les chatons ont été installés dans les cellules en premier lieu. Trouvez toute distribution de chatons dans n cellules d'origine qui ne contredit pas les données du journal.
Entrée
La première ligne contient un entier n (
\(2 \leq n \leq 150000\)) — nombre de chatons.
Les n−1 lignes suivantes contiennent des couples d'entiers x
i , y
i (
\(1 \leq x_i , y_i, \leq n,x_i \neq y_i\) ) — identifiants de chatons, entre les cellules dont la cloison a été retirée au jour i. Il est garanti que les chatons xi et yi ne sont pas dans la même cellule à la suite d'une précédente fusion de cellules.
Mentions légales
Imprimer n entiers distincts p
i (
\(1 \leq p_i \leq n\)), où p
i — l'identifiant du chaton qui vivait à l'origine dans la cellule numéro i. S'il y a plusieurs réponses possibles, écrivez-en une.
Remarque
Dans la réponse, par exemple, l'un des premiers établissements possibles de chatons est donné, il y a d'autres réponses. L'image ci-dessous montre comment les cellules ont été fusionnées pour ce placement initial de chatons. Veuillez noter qu'avec cet arrangement, les chatons qui sont devenus amis chaque jour selon le journal d'Asya sont dans des cellules adjacentes.
| Entrée |
Sortie |
5
14
25
3 1
4 5 |
3 1 4 2 5 |