[POI2011]INS-Inspection

题意翻译

点数为n的树上每条边长度都为一。对于每一个点,设当前点为s,求: 是否存在一个其余点的排列,使得排列中相邻两个点到s的路径没有重复部分。 若存在,输出所有点到s的距离之和 * 2 - 这里面最大的距离,否则输出-1。

题目描述

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

输入输出样例

输入样例 #1

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

输出样例 #1

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

说明