19174번 - Hamilton 스페셜 저지다국어

Tracker Smurf is planning his trip for next holidays.  He wants to spend exactly one night in each of the villages in SmurfLand. His trip can start and end in any village.  Villages in SmurfLand are connected by roads in such a way that there's exactly one path between any two villages.  The distance between any two directly connected villages is exactly one kilometer.  Tracker is so fast that he can travel up to three kilometers each day, but he is still not sure if that's enough to be able to spend a night in each village exactly once.  Help him find the answer.

First line of input contains an integer $n$ ($1 \leq n \leq 10^5$) -- the number of villages in SmurfLand. The next $n-1$ lines describe the roads.  $i$th input line ($i \in \{ 2, \ldots, n \}$) contains an integer $p_i$ ($1 \leq p_i < i$) which means that there is a road connecting villages $i$ and $p_i$.

On a single line output $n$ integers $q_1, q_2, \ldots, q_n$ ($1 \leq q_i \leq n$) specifying the sequence of villages for Tracker to spend the nights in (Tracker starts in village $q_1$ then goes to village $q_2$ and so on, finishing in village $q_n$). If it is not possible to plan Tracker's trip then on a single line output the word "NO" (without quotes).