An Animal Contest 7 P5 - Squirrel Scheming

View as PDF

Submit solution

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

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 N nodes. Define the cost of a permutation a of the first N integers to be \sum_{i=2}^N \text{dis}(a[i], a[i-1]) where \text{dis}(i, j) is the distance between nodes i and j in the tree. Among all permutations, find the one with the minimum cost. If there are multiple such permutations, output the lexicographically least one.


1 \le N \le 5 \times 10^5

Subtask 1 [30%]

1 \le N \le 3\,000

Subtask 2 [70%]

No additional constraints.

Input Specification

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

Output Specification

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

Sample Input

1 2
2 6
2 3
3 4
3 5

Sample Output

1 2 6 3 4 5


There are no comments at the moment.