18970번 - Emerging Tree 스페셜 저지다국어

Consider a set $V = \{1, \ldots, n\}$ of $n$ vertices, and a sequence of directed edges $e_1, \ldots, e_{n - 1}$. Let $G_0, \ldots, G_{n - 1}$ be a sequence of graphs such that $G_0$ is empty, and $G_i$ is obtained by introducing the edge $e_i$ into $G_{i - 1}$ for each $i = 1, \ldots, n - 1$. It is guaranteed that $G_{n - 1}$ is a rooted tree with all edges directed away from the root.

Your task is to find a suitable permutation $p_1, \ldots, p_n$ of the set $\{1, \ldots, n\}$. Let $S_i(v) = \{p_u \mid u$ can be reached from $v$ in $G_i\}$. A permutation $p_1, \ldots, p_n$ is called suitable if for any $i \in \{0, \ldots, n - 1\}$ and for any $v \in V$ we have that $S_i(v)$ consists of consecutive numbers (that is, $S_i(v) = \{l, l + 1, \ldots, r\}$ for some numbers $l$ and $r$).

The first line contains a single integer $n$ ($2 \leq n \leq 10^6$).

The next $n - 1$ lines describe the edges $e_1, \ldots, e_{n - 1}$. The $i$-th of these lines contains two integers $u_i$ and $v_i$ --- indices of the source and the target vertices of the edge $e_i$ ($1 \le u_i, v_i \le n$).

It is guaranteed that adding all $n - 1$ edges results in a rooted tree with edges directed away from the root.

If there is no suitable permutation, print the only word "No" in the only line.

Otherwise, print "Yes" on the first line. On the second line print $n$ integers $p_1, \ldots, p_n$ describing any suitable permutation.