{"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eRamesses knows a lot about problems involving trees (undirected connected graphs without cycles)!\u003c/p\u003e\u003cp\u003eHe created a new useful tree decomposition, but he does not know how to construct it, so he asked you for help!\u003c/p\u003e\u003cp\u003eThe decomposition is the splitting the edges of the tree in some simple paths in such a way that each two paths have at least one common vertex. Each edge of the tree should be in exactly one path.\u003c/p\u003e\u003cp\u003eHelp Remesses, find such a decomposition of the tree or derermine that there is no such decomposition.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains a single integer $$$n$$$ ($$$2 \\leq n \\leq 10^{5}$$$) the number of nodes in the tree.\u003c/p\u003e\u003cp\u003eEach of the next $$$nā-ā1$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \\leq a_i, b_i \\leq n$$$, $$$a_i \\neq b_i$$$)\u0026nbsp;ā the edges of the tree. It is guaranteed that the given edges form a tree.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eIf there are no decompositions, print the only line containing \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eNo\u003c/span\u003e\".\u003c/p\u003e\u003cp\u003eOtherwise in the first line print \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eYes\u003c/span\u003e\", and in the second line print the number of paths in the decomposition $$$m$$$. \u003c/p\u003e\u003cp\u003eEach of the next $$$m$$$ lines should contain two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \\leq u_i, v_i \\leq n$$$, $$$u_i \\neq v_i$$$) denoting that one of the paths in the decomposition is the simple path between nodes $$$u_i$$$ and $$$v_i$$$. \u003c/p\u003e\u003cp\u003eEach pair of paths in the decomposition should have at least one common vertex, and each edge of the tree should be presented in exactly one path. You can print the paths and the ends of each path in arbitrary order.\u003c/p\u003e\u003cp\u003eIf there are multiple decompositions, print any.\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\u003e4\n1 2\n2 3\n3 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYes\n1\n1 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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\u003e6\n1 2\n2 3\n3 4\n2 5\n3 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eNo\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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 2\n1 3\n1 4\n1 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYes\n4\n1 2\n1 3\n1 4\n1 5\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 tree from the first example is shown on the picture below: \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/b8f5881ed06332f005f8a31f229e4a2b?v\u003d1726347255\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e The number next to each edge corresponds to the path number in the decomposition. It is easy to see that this decomposition suits the required conditions.\u003c/p\u003e\u003cp\u003eThe tree from the second example is shown on the picture below: \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/84b1f8263ccc284a6d734e536b4d6f2e?v\u003d1726347255\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e We can show that there are no valid decompositions of this tree.\u003c/p\u003e\u003cp\u003eThe tree from the third example is shown on the picture below: \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/96ce0d9c8a70bce04fba5efdeda7e299?v\u003d1726347255\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e The number next to each edge corresponds to the path number in the decomposition. It is easy to see that this decomposition suits the required conditions.\u003c/p\u003e"}}]}