Equilibrium

There are city elections in Treetopia! Treetopia, as you
should know, is a quite unique country; there is
*exactly* one way of travelling between *every*
pair of cities! Two cities are said to be neighbouring if it is
possible to travel from one to the other without visiting any
other cities along the way, and the relationship between
neighbouring cities is really something special.

The elections result are now being counted, and in just a
short while the results will be announced on public
broadcasting. This year, an election observer is standing ready
in every of Treetopia’s $n$ cities to report on any problems
they find. You know that every observer is very particular
about the *order* that the results are announced. In
particular, an observer in city $i$ will count how many of the
$i^{\text {th}}$ city’s
neighbours are announced *before* city $i$ (denoted $b_ i$) as well as how many of its
neighbouring cities are announced *after* city
$i$ (denoted $a_ i$).

The observer will expect $a_ i$ to equal $b_ i$. In fact, for every number the two numbers differ, $|a_ i - b_ i|$, the observer will send an angry letter of complaint. Desperate to avoid mountains of useless mail, you wonder which ordering you should choose to minimize the total number of complaints received.

The first line of input contains a positive integer $n$ ($1 \leq n \leq 100\, 000$), the number of cities in Treetopia. Then follows $n-1$ lines, the $i^{\text {th}}$ of which contains two distinct integers $u_ i$ and $v_ i$ ($0 \leq u_ i, v_ i < n$), indicating that $u_ i$ and $v_ i$ are neighbouring cities.

A single line with $n$ space-separated integers, representing an order of the cities in Treetopia such that announcing the election results in this order minimize the number of received complaints. If there are several optimal orders, you can output any of them.

Sample Input 1 | Sample Output 1 |
---|---|

3 0 1 0 2 |
2 0 1 |