Inspection Batch Compilation commands

The railway network of the Byteotian Railways (BR) consists of bidirectional tracks connecting certain pairs of stations. Each pair of stations is connected by at most one segment of tracks. Furthermore, there is a unique route from every station to every other station. (The route may consist of several segments of tracks, but it may not pass through any station more than once.)

Byteasar is an undercover inspector of the BR. His job is to pick one of the stations (denote it by $S$) for centre of his operations and to travel to all other stations. His journey should be as follows:

• Byteasar starts in station $S$.
• Next, he picks one of the stations he did not yet control and goes to it along the shortest path (by train, of course), inspects the station, and then goes back to $S$.
• The crooked employees of BR warn one another of Byteasar's comings. To deceive them, Byteasar picks the next station for control in such a way that he sets off from the station $S$ in different direction than the last time, i.e., along a different segment of tracks leaving from $S$.
• Each station (except $S$) is inspected exactly once.
• After inspecting the last station Byteasar does not come back to $S$.

The travel time along every segment of tracks takes the same amount of time: one hour.

Byteasar intends to consider all the stations as the initial station $S$. For each of them he wants to know the order of inspecting the remaining stations that minimises the total travel time, provided that it is possible at all for that particular $S$.

Input

The first line of the standard input contains a single integer $n$ ($1 \le n \le 1\,000\,000$) that denotes the number of stations. These are numbered from $1$ to $n$. The following $n-1$ lines specify the track segments, one per line. Each of them holds two integers $a$,$b$ ($1 \le a,b \le n$, $a \neq b$), separated by a single space, indicating that there is a track segment connecting the stations $a$ and $b$. Each track segments appears exactly once in the description.

In tests worth at least 30% of the points it holds additionally that $n \le 2,000$.

Output

Your program should print $n$ lines on the standard output, each holding a single integer. The one in the $i$-th line should be the minimum number of hours Byteasar has to spend travelling to inspect the stations when $S=i$ - if inspecting them all is possible for $S=i$; if it is not, the $i$-th line should hold the number $-1$.

Example

For the input data:

9
3 6
2 4
2 6
2 5
1 7
2 7
8 9
7 8

the correct result is:

-1
23
-1
-1
-1
-1
-1
-1
-1

The figure illustrates the railway network as specified in the example. It is possible to inspect all the stations only for $S=2$. One optimal order of inspection is: $7,4,8,6,1,5,3,9$ . It results in $23$ hours of travel.

Task authors: Wojciech Rytter and Bartosz Szreder.