狐狸与完整树遍历

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定一棵包含 $n$ 个结点的树。记 $\operatorname{dist}(x,y)$ 为结点 $x,y$ 之间最短路径的边数。

请判断是否存在一个 $1\sim n$ 的排列 $p$，使得相邻两项以及首尾两项在树上的距离都不超过 $2$：

• 对每个 $1\le i<n$，有 $\operatorname{dist}(p_i,p_{i+1})\le2$；
• $\operatorname{dist}(p_n,p_1)\le2$。

若存在，输出任意一个满足条件的排列；否则报告无解。

输入格式

第一行包含一个整数 $n$。

接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示树边 $(u,v)$。

输出格式

若不存在满足条件的排列，输出一行 No。

否则先输出一行 Yes，再输出一行 $n$ 个整数，表示任意一个合法排列。

答案不区分 Yes、No 的字母大小写。

样例输入 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

数据范围

• $2\le n\le2\times10^5$；
• $1\le u,v\le n$，$u\ne v$；
• 输入保证构成一棵树。

题目来源：Codeforces 1819C。