{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eConsider an undirected tree. The following algorithm constructs a post-order traversal of the tree:\u003c/p\u003e\u003cpre class\u003d\"verbatim\"\u003e\u003cbr\u003efun dfs(v):\u003cbr\u003e mark v as used\u003cbr\u003e for u in neighbours(v):\u003cbr\u003e if u is not used:\u003cbr\u003e dfs(u)\u003cbr\u003e append v to order\u003cbr\u003e\u003c/pre\u003e\u003cp\u003eThe post-order traversal will be in the list \u003cspan class\u003d\"tex-font-style-it\"\u003eorder\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eYou are allowed to choose the order of neighbors for each vertex as well as the starting vertex. What is the lexicographically minimal \u003cspan class\u003d\"tex-font-style-it\"\u003eorder\u003c/span\u003e you can get?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of input contains one integer $$$T$$$ ($$$1 \\le T \\le 10^{5}$$$)\u0026nbsp;— the number of test cases you need to process. Description of the test cases follows.\u003c/p\u003e\u003cp\u003eThe first line of each test case contains a single integer $$$n$$$ ($$$2 \\le n \\le 2 \\cdot 10^{5}$$$)\u0026nbsp;— the number of vertices in the tree. \u003c/p\u003e\u003cp\u003eThe $$$i$$$-th of the next $$$n-1$$$ lines contains two integers $$$u_i, v_i$$$ ($$$1 \\le u_i, v_i \\le n$$$, $$$u_i \\ne v_i$$$), meaning that there is an undirected edge $$$(u_i, v_i)$$$ in the tree. It is guaranteed that the given graph is a tree.\u003c/p\u003e\u003cp\u003eThe sum of $$$n$$$ over all test cases in one test file does not exceed $$$2 \\cdot 10^{5}$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case print the lexicographically minimal order on a separate line.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n3\n1 3\n3 2\n3\n2 1\n1 3\n7\n1 2\n1 3\n2 4\n2 5\n3 6\n3 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 2 3 \n2 1 3 \n4 5 2 1 6 3 7 \n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eThe first test looks as follows:\u003c/p\u003e\u003cp\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/79abe9770b86aefcdb7ead86d2e46064?v\u003d1715630818\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/p\u003e\u003cp\u003eBy starting in vertex $$$1$$$ we can only get order $$$2\\ 3\\ 1$$$. By starting in vertex $$$2$$$ we can only get order $$$1\\ 3\\ 2$$$. By starting in vertex $$$3$$$ we can get two orders: $$$1\\ 2\\ 3$$$ and $$$2\\ 1\\ 3$$$. The lexicographically minimal of the four orders is $$$1\\ 2\\ 3$$$.\u003c/p\u003e\u003cp\u003eThe second test looks as follows:\u003c/p\u003e\u003cp\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/f5f52c2c35030e19b74199a002516f0d?v\u003d1715630818\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/p\u003e\u003cp\u003eBy starting in vertex $$$1$$$ we can get two orders: $$$2\\ 3\\ 1$$$ and $$$3\\ 2\\ 1$$$. By starting in vertex $$$2$$$ we can only get order $$$3\\ 1\\ 2$$$. By starting in vertex $$$3$$$ we can only get order $$$2\\ 1\\ 3$$$. The lexicographically minimal of the four orders is $$$2\\ 1\\ 3$$$.\u003c/p\u003e\u003cp\u003eThe third test looks as follows:\u003c/p\u003e\u003cp\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/d81874f55619c58f2190b0d08e651bbf?v\u003d1715630818\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/p\u003e\u003cp\u003eThe lexicographically minimal order is $$$4\\ 5\\ 2\\ 1\\ 6\\ 3\\ 7$$$ it can be obtained by starting in node $$$7$$$.\u003c/p\u003e"}}]}