Byteotian Railways Inspection

The Byteotian Railways (BR) network is a tree – a connected graph with no cycles – where each pair of stations is connected by at most one bidirectional track. Byteasar, an undercover inspector, selects a station S as his operations center. From S he must inspect every other station with a series of trips. Each trip (except the last) consists of traveling from S to some as-yet uninspected station along the unique (shortest) route, inspecting the station, and then returning to S. For the last station inspected he does not return to S.

However, to deceive the crooked BR employees, Byteasar must not leave S in the same direction (i.e. via the same track/neighbor) as he did on his immediately previous trip. In other words, if the first edge of the path for one trip is from S to a neighbor v, then the next trip must start with an edge from S to some neighbor other than v.

When S has only one neighbor, it is impossible to perform more than one round‐trip (unless the entire network has only 2 stations). Byteasar considers every station as a potential center S and, if it is possible to complete his journey, he wishes to minimize the total travel time. The travel time along every track is exactly one hour. It can be shown that the minimum total travel time if a valid ordering exists is given by

where \(d(S,u)\) is the distance (i.e. number of tracks) between stations S and u in the tree.

Input constraints: Assume the number of stations \(n\) satisfies \(1 \le n \le 10^5\). Stations are numbered from 1 to \(n\). The tree is given as \(n-1\) edges.

Note: For stations S where the journey is not possible (i.e. when S has only one neighbor and \(n>2\)), output -1.

inputFormat

The first line contains a single integer \(n\), the number of stations. Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) (\(1 \le u,v \le n\)) indicating that there is a bidirectional track between stations \(u\) and \(v\).

outputFormat

Output \(n\) space‐separated integers. The \(i\)-th integer is the minimum total travel time required when station \(i\) is chosen as the center S, or -1 if it is impossible to inspect all stations under the given constraints.

sample

2
1 2

1 1