← 返回题目列表

Codeforces · 1819/C

C. 狐狸和完整的树遍历

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

狐狸八重爬上了圣樱树。树是一个不包含环的无向连通图。

狐狸使用她的魔法力量在树周围移动。当且仅当这些顶点之间的距离不超过 $$$2$$$ 时,Yae 才能从顶点 $$$v$$$ 跳转到另一个顶点 $$$u$$$。换句话说,如果顶点 $$$v$$$ 和 $$$u$$$ 通过边连接,或者如果存在这样的顶点 $$$w$$$,即顶点 $$$v$$$ 和 $$$w$$$ 通过边连接,并且顶点 $$$u$$$ 和$$$w$$$ 通过边连接。

八重拿到樱花花瓣后,她想知道树 $$$v_1, v_2, \ldots, v_n$$$ 中是否存在循环路径,这样:

- 狐狸可以从顶点 $$$v_i$$$ 跳到顶点 $$$v_{i + 1}$$$,
- 狐狸可以从顶点 $$$v_n$$$ 跳到顶点 $$$v_1$$$,
- 所有 $$$v_i$$$ 都是成对不同的。

帮助狐狸确定所需的遍历是否存在。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) - 树的顶点数。

以下 $$$n - 1$$$ 行中的每一行都包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — 由边连接的顶点。保证这些边形成一棵树。

输出

在第一行,如果所需的树路由存在,则打印“Yes”(不带引号),否则打印“No”(不带引号)。

如果所需的树遍历存在,则在第二行打印 $$$n$$$ 不同整数的整数 $$$v_1, v_2, \ldots, v_n$$$ ($$$1 \le v_i \le n$$$) - 按遍历顺序排列的树的顶点。

如果有多次正确的遍历,则输出其中任意一个。

示例

输入 #1

5
1 2
1 3
3 4
3 5

输出 #1

Yes
4 5 1 2 3

输入 #2

3
1 2
1 3

输出 #2

Yes
1 2 3

输入 #3

15
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15

输出 #3

No

注意

第一个示例中的树如下所示。粗箭头表示狐狸的路线。

在第二个示例中,三个不同顶点的任何序列都是正确的路线,因为狐狸可以从任何顶点跳到任何顶点。

第三个示例的树如下所示。可以看出,它没有必需的路径。