Душное знойное лето молочного района Висконсина вызывает жажду у коров. 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$ описывает разветвление $i$ тремя целыми через пробел: $E_{i}$, $B1_{i}$, $B2_{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$ непосредственно связаны с ней и на расстоянии $2$. Трубы $4$, $5$ связаны с трубой $3$ и на расстоянии $3$.

Автор задачи: Rob Kolstad, 2008