Description

Farmer John's cows live on $n$ different pastures, numbered $1 \sim n$.

There are exactly $n-1$ undirected roads of unit length connecting these pastures, and from any pasture you can reach all others. In other words, the pastures and roads form a tree. The input specifies, for each pasture $i$, its parent $p_i$. The root has $p_i = 0$, meaning it has no parent.

There are $k$ political parties numbered $1 \sim k$. Each cow joins exactly one party; specifically, cow $i$ (at pasture $i$) belongs to party $a_i$. Each party has at least two cows. Every party wants to know its "range", defined as the distance (along the undirected roads) between the farthest pair of cows within that party.

Input Format

The first line contains two integers $n, k$.

Lines $2 \sim n+1$: line $i+1$ contains two integers $a_i, p_i$.

Output Format

Output $k$ lines. The $i$-th line contains a single integer, the range of party $i$.

6 2 
1 3 
2 1 
1 0 
2 1 
2 1 
1 5 

3 
2 

Hint

Constraints: $2 \le n \le 2 \times 10^5, 1 \le k \le \frac n2, 0 \le p_i \le n, 1 \le a_i \le k$.

Translated by ChatGPT 5