17984번 - 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^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.

The first line of input contains a positive integer n (1 ≤ n ≤ 100 000), the number of cities in Treetopia. Then follows n − 1 lines, the i^th of which contains two distinct integers u_i and v_i (0 ≤ u_i, v_i < n), indicating that u_i and v_i are neighbouring cities.

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.