← 返回题目列表

Codeforces · 981/C

C. 有用的分解

中文机器翻译题面 查看原题

拉美西斯对涉及树(无环的无向连通图)的问题了解很多!

他创建了一个新的有用的树分解,但他不知道如何构造它,所以他向你求助!

分解是将树的边分裂成一些简单的路径,使得每两条路径至少有一个公共顶点。树的每条边都应该位于一条路径中。

帮助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

注意

第一个示例中的树如下图所示: 每条边旁边的数字对应于分解中的路径编号。很容易看出这种分解符合所需的条件。

第二个示例中的树如下图所示: 我们可以证明该树没有有效的分解。

第三个示例中的树如下图所示: 每条边旁边的数字对应于分解中的路径编号。很容易看出这种分解符合所需的条件。