310341: CF1820E. The Fox and the Complete Tree Traversal

E. The Fox and the Complete Tree Traversaltime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

The fox Yae climbed the tree of the Sacred Sakura. A tree is a connected undirected graph that does not contain cycles.

The fox uses her magical powers to move around the tree. Yae can jump from vertex $v$ to another vertex $u$ if and only if the distance between these vertices does not exceed $2$. In other words, in one jump Yae can jump from vertex $v$ to vertex $u$ if vertices $v$ and $u$ are connected by an edge, or if there exists such vertex $w$ that vertices $v$ and $w$ are connected by an edge, and also vertices $u$ and $w$ are connected by an edge.

After Yae was able to get the sakura petal, she wondered if there was a cyclic route in the tree $v_1, v_2, \ldots, v_n$ such that:

• the fox can jump from vertex $v_i$ to vertex $v_{i + 1}$,
• the fox can jump from vertex $v_n$ to vertex $v_1$,
• all $v_i$ are pairwise distinct.

Help the fox determine if the required traversal exists.

Input

The first line contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) —the number of vertices of the tree.

Each of the following $n - 1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$) — vertices connected by an edge. It is guaranteed that these edges form a tree.

Output

On the first line, print "Yes" (without quotes) if the required route of the tree exists, or "No" (without quotes) otherwise.

If the required tree traversal exists, on the second line print $n$ integers of different integers $v_1, v_2, \ldots, v_n$ ($1 \le v_i \le n$) — the vertices of the tree in traversal order.

If there are several correct traversals, output any of them.

ExamplesInput

5
1 2
1 3
3 4
3 5

Output

Yes
4 5 1 2 3 

Input

3
1 2
1 3

Output

Yes
1 2 3

Input

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

Output

No

Note

The tree from the first example is shown below. The bold arrows indicate the fox's route.

In the second example, any sequence of three different vertices is a correct route, because the fox can jump from any vertex to any vertex.

The tree from the third example is shown below. It can be shown that there is no required route for it.

题目大意：
标题：E. 狐狸和完全树遍历

题目描述：狐狸Yae爬上了圣樱树。树是一个没有包含周期的连通无向图。狐狸可以使用她的魔法力量在树周围移动。Yae可以从顶点v跳到另一个顶点u，条件是这两个顶点之间的距离不超过2。换句话说，Yae可以从顶点v跳到顶点u，如果顶点v和u之间有一条边连接，或者存在这样的顶点w，使得顶点v和w之间有一条边连接，同时顶点u和w之间也有一条边连接。Yae得到了樱花瓣后，她想知道是否存在这样的循环遍历路线v1, v2, ..., vn，满足以下条件：
- 狐狸可以从顶点vi跳到顶点vi+1，
- 狐狸可以从顶点vn跳到顶点v1，
- 所有vi都是两两不同的。

输入数据格式：
第一行包含一个整数n（2≤n≤2×10^5）——树中顶点的数量。
接下来的n-1行，每行包含两个整数u和v（1≤u, v≤n，u≠v）——由边连接的顶点。保证这些边构成一棵树。

输出数据格式：
如果存在所需的树遍历路线，则在第一行打印“Yes”（不带引号），否则打印“No”（不带引号）。
如果存在所需的树遍历路线，则在第二行打印n个不同的整数v1, v2, ..., vn（1≤vi≤n）——树的遍历顺序。
如果有多个正确的遍历路线，输出其中任意一个。题目大意： 标题：E. 狐狸和完全树遍历 题目描述：狐狸Yae爬上了圣樱树。树是一个没有包含周期的连通无向图。狐狸可以使用她的魔法力量在树周围移动。Yae可以从顶点v跳到另一个顶点u，条件是这两个顶点之间的距离不超过2。换句话说，Yae可以从顶点v跳到顶点u，如果顶点v和u之间有一条边连接，或者存在这样的顶点w，使得顶点v和w之间有一条边连接，同时顶点u和w之间也有一条边连接。Yae得到了樱花瓣后，她想知道是否存在这样的循环遍历路线v1, v2, ..., vn，满足以下条件： - 狐狸可以从顶点vi跳到顶点vi+1， - 狐狸可以从顶点vn跳到顶点v1， - 所有vi都是两两不同的。 输入数据格式： 第一行包含一个整数n（2≤n≤2×10^5）——树中顶点的数量。 接下来的n-1行，每行包含两个整数u和v（1≤u, v≤n，u≠v）——由边连接的顶点。保证这些边构成一棵树。 输出数据格式： 如果存在所需的树遍历路线，则在第一行打印“Yes”（不带引号），否则打印“No”（不带引号）。 如果存在所需的树遍历路线，则在第二行打印n个不同的整数v1, v2, ..., vn（1≤vi≤n）——树的遍历顺序。 如果有多个正确的遍历路线，输出其中任意一个。