Description
Given a tree with n labeled nodes with labels from 1 to n, a Prufer code uniquely idetifies the tree by the following rule.
At step i, remove the leaf (the nodes with deg = 1) with the smallest label and set the i-th element of the Prüfer sequence to be the label of this leaf's neighbor until only two nodes left.
For example, the Prufer code of the tree below is {4, 4, 4, 5}. （the order of the leaf removed is 1, 2, 3, 4）
Kuo-chan wants to find the Prufer code of the given trees. Please help him.
Input
The first line contains a single integer n — the number of vertices.
Each of the next n - 1 lines contains two integer vi and ui — meaning there is an edge between vi and ui.
n <= 5000
1 <= vi, ui <= n
Output
The output should contains n - 2 distinct integers, meaning the Prufer code of the tree.
Remember to add new line in the end.