위스콘신 낙농 지역의 습하고 무더운 여름은 소들이 갈증을 풀게 합니다. Farmer John은 외양간 펌프로 맑고 차가운 물을 $N$개 분기 관에 보냅니다. $(3 \le N \le 99999)$, $N$은 홀수, 번호는 $1,\ldots,N$입니다. 물이 흐르며 여름 열기로 따뜻해집니다. Bessie는 가장 찬 물을 찾아 다른 어떤 소보다 날씨를 즐기려 합니다.

모든 관의 지도를 만들자 농장을 루트로 하는 트리이며 각 분기점에서 정확히 두 관이 나갑니다. 놀랍게도 관마다 길이는 정확히 한 단위이고 모든 $N$개가 어떻게든 관 트리에 연결됩니다.

연결 지도에서 모든 분기점과 끝점의 외양간으로부터 거리를 나열하세요. Bessie는 가장 찬 물을 찾는 데 씁니다.

관 끝은 분기점으로 들어가거나 수도꼭지이며 관 번호로 불립니다. 지도에는 $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)$. 관 $1$은 외양간과 연결되어 끝점 거리는 $1$입니다.

입력

• 줄 $1$: 공백으로 나눈 정수 $N$, $C$.

• 줄 $2,\ldots,C+1$: 줄 $i+1$은 공백으로 나눈 세 정수 $E_{i}$, $B1_{i}$, $B2_{i}$로 분기점 $i$를 설명합니다.

출력

• 줄 $1,\ldots,N$: 줄 $i$에 관 $i$ 끝점의 외양간으로부터 거리인 정수 하나.

예제

입력 1

5 2
3 5 4
1 2 3

출력 1

1
2
2
3
3

참고

입력은 다음 지도를 뜻합니다.

                    +------+
                    | 외양간 |
                    +------+
                       | 1
                       *
                    2 / \ 3
                         *
                      4 / \ 5

관 $1$은 항상 거리 $1$입니다. $2$, $3$은 $1$에 직접 연결되어 거리 $2$입니다. $4$, $5$는 $3$에 연결되어 거리 $3$입니다.

문제 작성자: Rob Kolstad, 2008