# Tree

Very easy

Execution time limit is 2 seconds

Runtime memory usage limit is 256 megabytes

The hanging tree contains $n(1≤n≤10_{6})$ vertices. Each vertex is colored in one of $n$ colors. For each vertex $v$ find the number of different colors, occurring in the subtree with root $v$.

## Input

The first line contains the number $n$. The next $n$ lines describe the vertices. The description of the vertex $i$ has the form $p_{i}c_{i}$, where $p_{i}$ is the parent number of the vertex $i$, and $c_{i}$ is the color of the vertex $i(1≤c_{i}≤n)$. For the root of the tree $p_{i}=0$.

## Output

Print $n$ numbers, denoting the number of different colors in the subtrees rooted at the vertices $1,2,...,n$.

## Examples

Input #1

Answer #1

Submissions 3K

Acceptance rate 27%