Las vacas del Granjero Juan están viviendo en ~N (2 \leq N \leq 200,000)~ pastizales convenientemente numerados ~1..N~. Exactamente ~N-1~ caminos de vacas bidireccionales (de longitud unitaria) conectan estos pastizales de varias maneras, y se puede llegar a cada pastizal desde cualquier otro pastizal recorriendo uno o mas de estos caminos (por lo tanto, los pastizales y caminos forman un grafo llamado un árbol).

La entrada para un conjunto particular de pastizales especificará el nodo padre ~P_i (0 \leq P_i \leq N)~ para cada pastizal. El nodo raíz estará especificado por tener nodo padre P_i == 0, lo cual quiere decir que no tiene padre.

Las vacas han organizado ~K (1 \leq K \leq N/2)~ partidos políticos distintos convenientemente numerados ~1..K~. Cada vaca se identifica con un solo partido político; la vaca i se identifica con el partido político ~A_i (1 \leq A_i \leq K)~. Cada partido político incluye al menos dos vacas.

Los partidos políticos se están organizando y quieren saber el 'rango' que cada partido cubre. El rango de un partido es la mayor distancia entre cualesquiera dos vacas dentro de ese partido (sobre los caminos de vacas).

Por ejemplo, suponga que el partido político 1 consiste de las vacas ~1,3,~ y ~6~, el partido político 2 consiste de las vacas ~2, 4,~ y ~5~, y los pastizales están conectados como sigue (las miembros del partido 1 están marcadas como –n-):

  -3-
   |
  -1-
 / | \
2  4  5
   |
  -6-

La mayor distancia entre dos pastizales del partido político ~1~ es ~3~ (entre las vacas ~3~ y ~6~), y la mayor distancia para el partido político ~2~ es ~2~ (entre las vacas ~2~ y ~4~, entre las vacas ~4~ y ~5~, y entre las vacas ~5~ y ~2~).

Ayude a las vacas a determinar los rangos de los partidos.

Entrada

• Línea 1: Dos enteros separados por espacio: ~N~ y ~K~

• Líneas 2..N+1: La línea i+1 contiene dos enteros separados por espacio: ~A_i~ y ~P_i~.

Ejemplo de Entrada

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

Salida

• Líneas 1..K: La línea ~i~ contiene un solo entero que es el rango del partido ~i~.

Ejemplo de Salida

3
2