Problem E
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.
Input
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.
Output
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 |
