{"problem":{"name":"Takahashi Tour","description":{"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 t","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc213_d"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc213_d","tags":[],"sample_group":[["4\n1 2\n4 2\n3 1","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."],["5\n1 2\n1 3\n1 4\n1 5","1 2 1 3 1 4 1 5 1"]],"created_at":"2026-03-03 11:01:13"}}