35101번 - To Be Discontinued 스페셜 저지다국어

The year is AD 3000. Humanity enjoys traveling among the stars via the network of interstellar spaceship routes. Due to recent advances in warp drive technology, however, the traditional spaceship routes are being gradually discontinued. You, a nostalgic voyager, have decided to take all the remaining routes before the planned discontinuation.

Currently, the interstellar routes form a tree-structured network among $n$ planets. That is, there are $n − 1$ bidirectional routes each connecting two planets, and by taking such routes several times, you can travel between any pair of planets. However, each route has now been assigned its final boarding time. If you are on a planet at time $t$, and $t$ does not exceed the final boarding time $e$ of a certain route starting there (i.e., $t ≤ e$), you can reach the other end of the route at time $t + 1$. You cannot use the route after the final boarding time.

In addition to the traditional spaceship routes, you can also use the new warp drive technology. Using the warp drive, you can instantly travel from any planet to a destination planet without spending any time, provided that you have already visited that destination at least once! You are currently on one of the n planets. Because you have not visited any other planets prior to this journey, you must first travel to a planet via the spaceship routes before you can warp to it.

Starting your journey at time $0$, can you traverse all the spaceship routes before their respective final boarding times? Since the network forms a tree, the question is equivalent to asking whether you can visit all the planets. If such a journey is possible, find the order in which you should visit the planets.

Figure E.1. The first test case of Sample Input 1

Figure E.1 illustrates the first test case of Sample Input 1. The left part shows the network of interstellar spaceship routes. Each line segment is labeled with an integer representing the final boarding time of the route. The right part shows one way to traverse all the routes. Dotted lines in the right part represent warps, and the notation “$t \dots t + 1$” represents taking the route that departs at time $t$ and arrives at time $t + 1$.

The input consists of at most $50$ test cases, each in the following format.

$n$

$p_2$ $e_2$

$\vdots$

$p_n$ $e_n$

The integer $n$ ($2 ≤ n ≤ 1000$) on the first line is the number of planets connected by the network of interstellar spaceship routes. The planets are numbered $1$ through $n$ and you are initially on planet $1$. The $2$-nd to the $n$-th lines describe the interstellar spaceship routes, where integers $p_i$ ($1 ≤ p_i < i$) and $e_i$ ($0 ≤ e_i ≤ 1000$) mean that there exists a route between planets $i$ and $p_i$ with the final boarding time $e_i$, for $i = 2, \dots , n$.

The end of the input is indicated by a line consisting only of a zero.

For each test case, if it is possible to traverse all the routes meeting their respective final boarding times, output yes in the first line; otherwise, output no.

If that is possible, output in the next line a list of the planet numbers from $2$ to $n$ in the order of your first visits, separated by a space. If there are multiple ways, output any one of them.