{"raw_statement":[{"iden":"problem statement","content":"Takahashi has an ability to generate a tree using a permutation $(p_1,p_2,...,p_n)$ of $(1,2,...,n)$, in the following process:\nFirst, prepare Vertex $1$, Vertex $2$, ..., Vertex $N$. For each $i=1,2,...,n$, perform the following operation:\n\n*   If $p_i = 1$, do nothing.\n*   If $p_i \\neq 1$, let $j'$ be the largest $j$ such that $p_j < p_i$. Span an edge between Vertex $i$ and Vertex $j'$.\n\nTakahashi is trying to make his favorite tree with this ability. His favorite tree has $n$ vertices from Vertex $1$ through Vertex $n$, and its $i$\\-th edge connects Vertex $v_i$ and $w_i$. Determine if he can make a tree isomorphic to his favorite tree by using a proper permutation. If he can do so, find the lexicographically smallest such permutation."},{"iden":"notes","content":"For the definition of isomorphism of trees, see [wikipedia](https://en.wikipedia.org/wiki/Graph_isomorphism). Intuitively, two trees are isomorphic when they are the \"same\" if we disregard the indices of their vertices."},{"iden":"constraints","content":"*   $2 \\leq n \\leq 10^5$\n*   $1 \\leq v_i, w_i \\leq n$\n*   The given graph is a tree."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$n$\n$v_1$ $w_1$\n$v_2$ $w_2$\n$:$\n$v_{n-1}$ $w_{n-1}$"},{"iden":"sample input 1","content":"6\n1 2\n1 3\n1 4\n1 5\n5 6"},{"iden":"sample output 1","content":"1 2 4 5 3 6\n\nIf the permutation $(1, 2, 4, 5, 3, 6)$ is used to generate a tree, it looks as follows:\n![image](https://img.atcoder.jp/arc095/db000b879402aed649a1516620eb1e21.png)\nThis is isomorphic to the given graph."},{"iden":"sample input 2","content":"6\n1 2\n2 3\n3 4\n1 5\n5 6"},{"iden":"sample output 2","content":"1 2 3 4 5 6"},{"iden":"sample input 3","content":"15\n1 2\n1 3\n2 4\n2 5\n3 6\n3 7\n4 8\n4 9\n5 10\n5 11\n6 12\n6 13\n7 14\n7 15"},{"iden":"sample output 3","content":"\\-1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}