Journey of the Robber

Monopolis is a beautiful and wealthy country. Among its notable features is its layout: $N$ cities are connected by $N-1$ roads of equal length, so any two cities can be reached from each other.

Another distinctive feature of Monopolis is that each city has one bank, and no two banks hold the same amount of money. Therefore, each city can be given a distinct number from 1 to $N$ that represents its wealth ranking. City 1 has the least money, and city $N$ has the most.

Rob is planning a "business trip" to Monopolis. Rob's business is robbing, specifically robbing banks. Rob is an ambitious robber with a strict method: he only targets banks with more money than the one he just robbed. After robbing city $i$, he moves to the closest city with more money than $i$. If several such cities are at the same distance, he chooses the one with the least money. If no city is richer than $i$, he stays in the same city and reflects on his actions.

Rob follows this method strictly, and he asks for your help with his trip. For each city $i$, he wants to know which city he would visit next if his first robbery is in city $i$.

The first line contains an integer $N$ ($1 \le N \le 10^5$), the number of cities in Monopolis. Each city is identified by a distinct integer from 1 to $N$, in increasing order of wealth.

Each of the next $N-1$ lines contains two integers $U$ and $V$ ($1 \le U, V \le N$, $U \ne V$), meaning there is a two-way road between cities $U$ and $V$. The given roads guarantee a path between every pair of cities.

Print a single line with $N$ integers. The $i$-th integer is the next city Rob would visit if his first robbery is in city $i$.