맑고 차가운 물

위스콘신 낙농 지대의 덥고 습한 여름이면 젖소들이 갈증을 느끼기 때문에, 농부 John은 헛간에서 맑고 차가운 물을 퍼 올려 파이프 망으로 흘려보내 소들을 시원하게 해 준다. 파이프는 $N$개($3 \le N \le 99999$, $N$은 홀수)이며 $1 \dots N$번으로 번호가 매겨져 있다. 물이 파이프를 따라 흐르는 동안 여름 열기에 데워지므로, Bessie는 가장 차가운 물을 찾기 위해 망의 모든 지점이 헛간에서 얼마나 떨어져 있는지 알고 싶어 한다.

파이프들은 헛간을 뿌리로 하는 이진 트리를 이룬다. 모든 분기점에서는 정확히 두 개의 파이프가 뻗어 나가고, 모든 파이프의 길이는 정확히 $1$이며, $N$개의 파이프는 모두 이 하나의 트리로 연결되어 있다.

각 파이프의 끝점은 분기점이거나 열린 꼭지이며, 그 끝점은 해당 파이프의 번호로 식별된다. $1$번 파이프는 헛간에 연결되어 있고, 그 끝점에서 헛간까지의 거리는 $1$이다.

지도에는 $C$개($1 \le C \le N$)의 분기점이 나열된다. 각 분기점은 세 정수로 주어진다. 어떤 파이프의 끝점 $E_i$($1 \le E_i \le N$)와, 그 끝점에서 뻗어 나가는 두 파이프 $B1_i$, $B2_i$($2 \le B1_i \le N$, $2 \le B2_i \le N$)이다. 파이프가 분기하면 거리가 이어져, $B1_i$와 $B2_i$의 끝점은 $E_i$의 끝점보다 헛간에서 $1$만큼 더 멀다.

이 지도를 이용하여 모든 파이프의 끝점에서 헛간까지의 거리를 구하라.

• 첫째 줄: 두 정수 $N$과 $C$가 공백으로 구분되어 주어진다.
• 둘째 줄부터 $C+1$째 줄까지: $i+1$째 줄은 하나의 분기점을 세 정수 $E_i$, $B1_i$, $B2_i$로 설명한다. 파이프 $E_i$의 끝점이 분기점이며, 그곳에서 파이프 $B1_i$과 $B2_i$이 뻗어 나간다.

• 첫째 줄부터 $N$째 줄까지: $i$째 줄에는 헛간에서 파이프 $i$의 끝점까지의 거리를 나타내는 정수 하나를 출력한다.

첫 번째 예제는 다음 파이프 지도를 나타낸다.

+------+
| Barn |
+------+
   | 1
   *
2 / \ 3
     *
  4 / \ 5

$1$번 파이프는 항상 헛간에서 거리가 $1$이다. $2$번과 $3$번 파이프는 $1$번 파이프의 끝점에서 분기하므로 거리가 $2$이다. $4$번과 $5$번 파이프는 $3$번 파이프의 끝점에서 분기하므로 거리가 $3$이다.