Inspection

The railway network of the Byteotian Railways (BR) is a set of two-way tracks. Each track directly connects a pair of stations, at most one track joins any given pair of stations, and between every two stations there is exactly one route that never visits a station twice. In other words, the network is a tree with $n$ stations.

Byteasar is an undercover BR inspector. He chooses one station as his base $S$ and must inspect every other station. His tour works like this:

• He starts at station $S$.
• He repeatedly picks a station he has not inspected yet, rides to it along the shortest route, inspects it, and rides back to $S$.
• Dishonest employees tip one another off, so to stay unpredictable Byteasar must leave $S$ along a different track than he used on the previous trip. That is, two consecutive trips may not start down the same track out of $S$.
• Every station other than $S$ is inspected exactly once.
• After inspecting the final station he does not return to $S$.

Riding along any single track takes exactly one hour.

Byteasar will consider every station as a possible base $S$. For each $S$, find the smallest possible total travelling time of a valid tour, or report that no valid tour exists for that $S$.

The first line contains an integer $n$ ($1 \le n \le 1{,}000{,}000$), the number of stations, numbered from $1$ to $n$. Each of the next $n-1$ lines contains two integers $a$ and $b$ ($1 \le a, b \le n$, $a \ne b$) separated by a single space, describing a track that directly connects stations $a$ and $b$. Every track is listed exactly once.

Print $n$ lines. Line $i$ must contain a single integer: the minimum total number of hours Byteasar needs to inspect every station when his base is $S = i$, or $-1$ if no valid tour exists for $S = i$.

The figure shows the network from the sample. A full inspection tour exists only for $S = 2$; one optimal order of inspection is $7, 4, 8, 6, 1, 5, 3, 9$, which takes $23$ hours.