#434 Spliting a tree

Statement

Statement language

You are given a tree $T$ with $N$ vertices numbered $1,2,\cdots,N$ .

Choose a vertex $v$ and a nonnegative integer $k$ . Remove every vertex whose distance from $v$ is at most $k$ , together with every edge incident to a removed vertex. The distance between two vertices is the number of edges on the unique simple path connecting them.

For every vertex $v$ , find the minimum $k$ such that the remaining graph has at least two connected components. If no such $k$ exists, the answer for $v$ is $-1$ .

The empty graph has zero connected components.

Input

The input is given from Standard Input in the following format:

$N$ $u_1\ v_1$ $u_2\ v_2$

Output

Let $A_i$ be the answer for vertex $i$ . Print $A_1,A_2,\cdots,A_N$ on one line, separated by spaces.

Constraints

$1 \leq N \leq 500\,000$ .
$1 \leq u_i,v_i \leq N$ ().

Subtasks

#	Score	Constraints
1	12	$N \leq 200$ .
2	37	$N \leq 5\,000$ .
3	51	No additional constraints.

Samples

Sample 1

Input

1

Output

-1

Removing the only vertex leaves the empty graph, so at least two connected components can never remain.

Sample 2

Input

Output

-1 0 0 -1

Removing vertex $2$ or vertex $3$ alone splits the tree into two components. From either leaf, no value of $k$ leaves at least two components.

Sample 3

Input

Output

2 0 0 1 1