The Fox and the Complete Tree Traversal
Contest: Codeforces Round 866 (Div. 1)
Difficulty rating: 2400
Tags: constructive algorithms, dp, implementation, math, trees

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 format:
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 format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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.

Example input:
5
1 2
1 3
3 4
3 5

Example output:
Yes
4 5 1 2 3

Example input:
3
1 2
1 3

Example output:
Yes
1 2 3

Editorial:
Note that if the tree contains the subgraph shown below, then there is no answer. To prove this it is enough to consider all possible cases for how a cyclic route can pass through the upper vertex and understand that it is impossible to construct such route.
Let's assume that the tree does not contain the subgraph shown. It is easy to see that in this case, the tree can be represented as a path and vertices directly attached to it. To check that the tree can be represented in this way, we will find the diameter of the tree and check that all other vertices are directly connected to it. Now we need to learn how to build a cyclic route.
Number the vertices of the diameter from $$$1$$$ to $$$k$$$ in the order of traversal of the diameter from one end to the other. Now let's build the route as follows. Firstly, visit vertex $$$1$$$, then visit all vertices not on the diameter attached to vertex $$$2$$$, then move to vertex $$$3$$$, then to all vertices not on the diameter attached to vertex $$$4$$$, and so on. When we reach the end of the diameter, we will visit all vertices of the diameter with even numbers, as well as all vertices of the tree not on the diameter attached to the vertices of the diameter with odd numbers. Now let's make the same route in the opposite direction along the diameter, but through vertices of a different parity, which reaches vertex $$$2$$$.
Time complexity: $$$\mathcal{O}(n)$$$.