{"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\u003e拉美西斯对涉及树(无环的无向连通图)的问题了解甚多!\u003c/p\u003e\u003cp\u003e他创建了一种新的有用的树分解方法,但不知道如何构造它,所以向你求助!\u003c/p\u003e\u003cp\u003e这种分解是将树的边拆分为一些简单路径,使得每两条路径至少有一个公共顶点。树的每条边应该恰好属于一条路径。\u003c/p\u003e\u003cp\u003e帮助拉美西斯,找到这样的树分解,或确定不存在这样的分解。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含一个整数 $$$n$$$($$$2 \\leq n \\leq 10^{5}$$$)表示树中的节点数。\u003c/p\u003e\u003cp\u003e接下来的 $$$n - 1$$$ 行中,每行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$($$$1 \\leq a_i, b_i \\leq n$$$,$$$a_i \\neq b_i$$$)— 树的边。保证给定的边构成一棵树。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e如果不存在分解,输出包含 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eNo\u003c/span\u003e\" 的唯一一行。\u003c/p\u003e\u003cp\u003e否则,在第一行输出 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eYes\u003c/span\u003e\",在第二行输出分解中路径的数量 $$$m$$$。\u003c/p\u003e\u003cp\u003e接下来的 $$$m$$$ 行中,每行包含两个整数 $$$u_i$$$,$$$v_i$$$($$$1 \\leq u_i, v_i \\leq n$$$,$$$u_i \\neq v_i$$$)表示分解中的一条路径是节点 $$$u_i$$$ 和 $$$v_i$$$ 之间的简单路径。\u003c/p\u003e\u003cp\u003e分解中的每对路径应至少有一个公共顶点,树的每条边应该恰好属于一条路径。可以以任意顺序打印路径和每条路径的端点。\u003c/p\u003e\u003cp\u003e如果存在多个分解,输出任意一个即可。\u003c/p\u003e"}},{"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\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"}},{"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"}},{"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"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e第一个示例中的树如下图所示:\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/b8f5881ed06332f005f8a31f229e4a2b?v\u003d1720471654\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e 每条边旁边的数字对应分解中的路径编号。很容易看出,这种分解符合所需条件。\u003c/p\u003e\u003cp\u003e第二个示例中的树如下图所示:\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/84b1f8263ccc284a6d734e536b4d6f2e?v\u003d1720471654\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e 我们可以证明这棵树没有有效的分解。\u003c/p\u003e\u003cp\u003e第三个示例中的树如下图所示:\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/96ce0d9c8a70bce04fba5efdeda7e299?v\u003d1720471654\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e 每条边旁边的数字对应分解中的路径编号。很容易看出,这种分解符合所需条件。\u003c/p\u003e"}}]}