{"raw_statement":[{"iden":"problem statement","content":"The Republic of AtCoder has $N$ cities numbered $1$ through $N$ and $N-1$ roads numbered $1$ through $N-1$. Road $i$ connects City $A_i$ and City $B_i$ bidirectionally. It is guaranteed that one can travel between every pair of cities using roads.\nTakahashi will depart City $1$ and have a journey by repeating the following.\n\n*   If there are unvisited cities that are directly connected to the city Takahashi is in now, he goes to the city with the smallest number among those cities.\n*   Otherwise,\n    *   if he is in City $1$, he ends the journey;\n    *   otherwise, he goes to the city he was in just before visiting the current city for the first time.\n\nFind the sequence of cities visited by Takahashi in the order he visits them."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 2\\times 10^5$\n*   $1\\leq A_i,B_i \\leq N$\n*   It is possible to travel between every pair of cities using roads."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $B_1$\n$\\vdots$\n$A_{N-1}$ $B_{N-1}$"},{"iden":"sample input 1","content":"4\n1 2\n4 2\n3 1"},{"iden":"sample output 1","content":"1 2 4 2 1 3 1\n\nHis journey will be as follows.\n\n*   Start in City $1$.\n*   The unvisited cities directly connected to City $1$ are City $2$ and $3$. Go to the city with the smaller number, that is, City $2$.\n*   The unvisited city directly connected to City $2$ is City $4$. Go there.\n*   There is no unvisited city directly connected to City $4$. Go back to City $2$.\n*   There is no unvisited city directly connected to City $2$. Go to City $1$, where he was in just before visiting City $2$ for the first time.\n*   The unvisited city directly connected to City $1$ is City $3$. Go there.\n*   There is no unvisited city directly connected to City $3$. Go back to City $1$.\n*   There is no unvisited city directly connected to City $1$. End the journey."},{"iden":"sample input 2","content":"5\n1 2\n1 3\n1 4\n1 5"},{"iden":"sample output 2","content":"1 2 1 3 1 4 1 5 1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}