题目描述

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$.

输入格式

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\ne 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$.

输出格式

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$.

题目大意

一棵 $n$ 个节点的树，行动中心 $S$ 从 $1$ 至 $N$。从 $S$ 出发前往任意一个未标记到的点（沿树上两点的唯一路径走），标记该节点，然后返回 $S$。相邻两次行动所经过的道路不允许有重复，最后一次标记后不需要返回，求路程总和的最小值。

第 $i$ 行输出行动中心为 $i$ 时的答案，如果不可能则输出 $-1$。

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

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

提示