409479: GYM103577 E Molecules

Tomi is a famous scientific working with open-chain compounds, which generally speaking are molecules which do not form cycles between their atoms. Tomi is very interested on solving the famous protein folding problem, and for that purpose, he is developing a method to organize an open-chain compound into a list which is as balanced as possible. A single atom is balanced if exactly half of its neighbors appear to its left on the list, and the other half to the right (atoms with an odd number of neighbors will never be balanced). A list is maximally balanced if it contains as many balanced nodes as possible. For example:

A possible solution: $$$7,6,5,3,4,0,2,1$$$

In the solution above, nodes $$$4$$$ and $$$0$$$ are balanced since $$$3$$$ appears before $$$4$$$ and $$$0$$$ appears after. Similarly, $$$1$$$ and $$$2$$$ appear after $$$0$$$, and $$$5$$$ and $$$4$$$ appears before. Tomi needs your help to develop an efficient algorithm to compute a maximally balanced list representation of a very big molecule.

The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 5*10^5$$$), the number of atoms. Next, there will be $$$n - 1$$$ lines, with two integers $$$u$$$ and $$$v$$$, which represent a link from atom $$$u$$$ to atom $$$v$$$ ($$$0 \leq u, v < n$$$).

Print exactly $$$n$$$ integers separated by space, which represent the maximally balanced list.

8
0 1
0 2
0 4
0 5
4 3
5 6
5 7

3 4 5 0 1 2 6 7