Competitions

# Trees: Depth First Search

# Tree

The hanging tree contains **n** (**1** ≤ **n** ≤ `10`

) vertices. Each vertex is colored in one of ^{6}**n** colors. For each vertex **v** find the number of different colors, occurring in the subtree with root **v**.

#### Input

First line contains number **n**. Next **n** lines describe the vertices. The description of the vertex **i** has a form `p`

, where _{i} c_{i}`p`

is the parent number of vertex _{i}**i**, and `c`

is the color of vertex _{i}**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**.

Input example #1

5 2 1 3 2 0 3 3 3 2 1

Output example #1

1 2 3 1 1

Input example #2

1 0 1

Output example #2

1

Input example #3

2 0 1 1 1

Output example #3

1 1

Input example #4

2 0 1 1 2

Output example #4

2 1