## An Animal Contest 7 P5 - Squirrel Scheming

View as PDF

Points: 17 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

After foiling the squirrels' plans several times it is now time for the counterattack! From Julian's data it can be seen that there exists a big red button in the shape of an acorn — which possesses the ability to teleport them to who knows where — somewhere on the squirrel fleet (for emergency food stash purposes). William is currently trying to plot the shortest counter-invasion path through the squirrel armada; however, he has extreme difficulties doing math of any kind ...

Given is an unweighted tree with nodes. Define the cost of a permutation of the first integers to be where is the distance between nodes and in the tree. Among all permutations, find the one with the minimum cost. If there are multiple such permutations, output the lexicographically least one.

#### Input Specification

The first line of input will contain a single integer . The following lines will each contain spaced out integers , denoting an edge between nodes and .

#### Output Specification

Output one line with spaced out integers, the lexicographically least permutation that incurs the minimum cost.

#### Sample Input

6
1 2
2 6
2 3
3 4
3 5

#### Sample Output

1 2 6 3 4 5