题目描述

农夫约翰的奶牛住在$\red{N (2 <= N <= 200,000)}$片不同的草地上，标号为$\red{1}$到$\red{N}$。恰好有$\red{N-1}$条单位长度的双向道路，用各种各样的方法连接这些草地。

而且从每片草地出发都可以抵达其他所有草地。也就是说，这些草地和道路构成了一种叫做树的图。输入包含一个详细的草地的集合，详细说明了每个草地的父节点$\red{P_i (0 <= P_i <= N)}$。

根节点的$\red{P_i == 0, }$表示它没有父节点。因为奶牛建立了$\red{1}$到$\red{K}$一共$\red{K (1 <= K <= N/2)}$个政党。每只奶牛都要加入某一个政党，其中， 第$\red{i}$只奶牛属于第$\red{A_i (1 <= A_i <= K)}$个政党。而且每个政党至少有两只奶牛。

这些政党互相吵闹争。每个政党都想知道自己的"范围"有多大。其中，定义一个政党的范围是这个政党离得最远的两只奶牛（沿着双向道路行走）的距离。

比如说，记为政党$\red{1}$包含奶牛$\red{1，}$$\red{3}$和$\red{6，}$政党$\red{2}$包含奶牛$\red{2，}$$\red{4}$和$\red{5}$。这些草地的连接方式如下图所 示（政党$\red{1}$由$\red{-n-}$表示）：

政党$\red{1}$最大的两只奶牛的距离是$\red{3}$（也就是奶牛$\red{3}$和奶牛$\red{6}$的距离）。政党$\red{2}$最大的两只奶牛的距离是$\red{2}$（也就是奶牛$\red{2}$和$\red{4，}$$\red{4}$和$\red{5，}$还有$\red{5}$和$\red{2}$之间的距离）。

帮助奶牛们求出每个政党的范围。

输入格式

第一行: 两个由空格隔开的整数: $\red{N }$和 $\red{K }$

第$\red{2}$到第$\red{N+1}$行: 第$\red{i+1}$行包含两个由空格隔开的整数: $\red{A_i}$和$\red{P_i}$

输出格式

第$\red{1}$到第$\red{K}$行: 第$\red{i}$行包含一个单独的整数，表示第$\red{i}$个政党的范围。

样例

输入样例

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

输出样例

3
2