{"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\u003eI see a pink boar and I want it painted black. Black boars look much more awesome and mighty than the pink ones. Since Jaggy became the ruler of the forest, he has been trying his best to improve the diplomatic relations between the forest region and the nearby ones. \u003c/p\u003e\u003cp\u003eSome other rulers, however, have requested too much in return for peace between their two regions, so he realized he has to resort to intimidation. Once a delegate for diplomatic relations of a neighboring region visits Jaggy’s forest, if they see a whole bunch of black boars, they might suddenly change their mind about attacking Jaggy. Black boars are really scary, after all. \u003c/p\u003e\u003cp\u003eJaggy’s forest can be represented as a tree (connected graph without cycles) with \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e vertices. Each vertex represents a boar and is colored either black or pink. Jaggy has sent a squirrel to travel through the forest and paint all the boars black. The squirrel, however, is quite unusually trained and while it traverses the graph, it changes the color of every vertex it visits, regardless of its initial color: pink vertices become black and black vertices become pink. \u003c/p\u003e\u003cp\u003eSince Jaggy is too busy to plan the squirrel’s route, he needs your help. He wants you to construct a walk through the tree starting from vertex \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e such that in the end all vertices are black. A walk is a sequence of vertices, such that every consecutive pair has an edge between them in a tree.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of input contains integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 200 000\u003c/span\u003e), denoting the number of vertices in the tree. The following \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e integers, which represent the color of the nodes.\u003c/p\u003e\u003cp\u003eIf the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th integer is \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e, if the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th vertex is black and \u003cspan class\u003d\"tex-span\"\u003e - 1\u003c/span\u003e if the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th vertex is pink.\u003c/p\u003e\u003cp\u003eEach of the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/span\u003e lines contains two integers, which represent the indexes of the vertices which are connected by the edge. Vertices are numbered starting with \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput path of a squirrel: output a sequence of visited nodes\u0027 indexes in order of visiting. In case of all the nodes are initially black, you should print \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e. Solution is guaranteed to exist. If there are multiple solutions to the problem you can output any of them provided length of sequence is not longer than \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e7\u003c/sup\u003e\u003c/span\u003e.\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\u003e5\n1\n1\n-1\n1\n-1\n2 5\n4 3\n2 4\n4 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 4 2 5 2 4 3 4 1 4 1\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\u003eAt the beginning squirrel is at node 1 and its color is black. Next steps are as follows: \u003c/p\u003e\u003cul\u003e \u003cli\u003e From node \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e we walk to node \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e and change its color to pink. \u003c/li\u003e\u003cli\u003e From node \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e we walk to node \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e and change its color to pink. \u003c/li\u003e\u003cli\u003e From node \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e we walk to node \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e and change its color to black. \u003c/li\u003e\u003cli\u003e From node \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e we return to node \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e and change its color to black. \u003c/li\u003e\u003cli\u003e From node \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e we walk to node \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e and change its color to black. \u003c/li\u003e\u003cli\u003e We visit node \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e and change its color to black. \u003c/li\u003e\u003cli\u003e We visit node \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e and change its color to pink. \u003c/li\u003e\u003cli\u003e We visit node \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e and change its color to pink. \u003c/li\u003e\u003cli\u003e We visit node \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e and change its color to black. \u003c/li\u003e\u003cli\u003e We visit node \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e and change its color to black. \u003c/li\u003e\u003c/ul\u003e"}}]}