Quiet Yarn Routes

Time limit: 2000 msMemory limit: 256 MB

Gats has a cat tree with $N$ cushions numbered $1, 2, \ldots, N$ . Cushion $1$ is the top cushion. For each $i$ with $2 \le i \le N$ , there is a single passage from cushion $P_i$ to cushion $i$ , and that passage has yarn color $C_i$ .

A cushion $u$ is an ancestor of a cushion $v$ if $u = v$ or following passages upward from $v$ can reach $u$ .

For a fixed cushion $v$ , Gats may choose any ancestor $u$ of $v$ and walk downward along the unique path from $u$ to $v$ . The chosen route is quiet if no yarn color appears on more than one passage of that path. If $u = v$ , the path contains no passages and is quiet.

For every cushion $v$ with $1 \le v \le N$ , let $A_v$ be the number of ancestors $u$ of for which the route from to is quiet. Compute all values .

Input

The first line contains an integer $N$ ( $1 \le N \le 2 \times 10^5$ ), the number of cushions.

The next $N - 1$ lines describe cushions in this order. The line for cushion contains two integers and (, ), meaning that the passage from cushion to cushion has yarn color .

Output

Print $N$ integers $A_1, A_2, \ldots, A_N$ in one line, separated by spaces.

Samples

Sample 1

Input

Output

1 2 2 3 3

For cushion $5$ , the ancestors are $1, 2, 4, 5$ . The route from $1$ to $5$ uses colors $7, 3, 7$ , so it is not quiet. Starting from , , or is quiet, so .

Quiet Yarn Routes

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2