拉美西斯对涉及树(无环的无向连通图)的问题了解很多!
他创建了一个新的有用的树分解,但他不知道如何构造它,所以他向你求助!
分解是将树的边分裂成一些简单的路径,使得每两条路径至少有一个公共顶点。树的每条边都应该位于一条路径中。
帮助Remesses,找到这样一个树的分解或derermine,不存在这样的分解。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^{5}$$$) 树中的节点数。
接下来的 $$$n - 1$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$) — 树的边缘。保证给定的边形成一棵树。
输出
如果没有分解,则打印唯一包含“No”的行。
否则在第一行打印“Yes”,并在第二行打印分解$$$m$$$中的路径数。
接下来的 $$$m$$$ 行应包含两个整数 $$$u_i$$$、$$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$) 表示分解中的路径之一是节点 $$$u_i$$$ 和$$$v_i$$$。
分解中的每一对路径应至少有一个公共顶点,并且树的每条边应恰好出现在一条路径中。您可以按任意顺序打印路径和每个路径的末端。
如果有多个分解,则打印任何分解。
示例
输入 #1
4 1 2 2 3 3 4
输出 #1
Yes 1 1 4
输入 #2
6 1 2 2 3 3 4 2 5 3 6
输出 #2
No
输入 #3
5 1 2 1 3 1 4 1 5
输出 #3
Yes 4 1 2 1 3 1 4 1 5
注意
第一个示例中的树如下图所示: 每条边旁边的数字对应于分解中的路径编号。很容易看出这种分解符合所需的条件。
第二个示例中的树如下图所示: 我们可以证明该树没有有效的分解。
第三个示例中的树如下图所示: 每条边旁边的数字对应于分解中的路径编号。很容易看出这种分解符合所需的条件。