Parne, upalne lata mleczarskiej części Wisconsin pobudzają pragnienie krów. Farmer John pompuje z obory czystą zimną wodę do $N$ rozgałęzionych rur, $(3 \le N \le 99999)$, $N$ nieparzyste, numerowanych $1,\ldots,N$. Letni upał ogrzewa płynącą wodę. Bessie szuka najzimniejszej, by cieszyć się pogodą bardziej niż inne krowy.

Mapa wszystkich rur to drzewo z korzeniem na farmie, z dokładnie dwiema wychodzącymi rurami w każdym rozgałęzieniu. Zaskakująco każda ma dokładnie jednostkę długości; wszystkie $N$ są jakoś połączone z drzewem.

Podaj z mapy odległości każdego rozgałęzienia i końca od obory. Bessie użyje ich do szukania najzimniejszej wody.

Koniec rury może wejść w rozgałęzienie albo być kranem i nosi numer rury. Mapa ma $C$ połączeń, $(1 \le C \le N)$, każde trzy całkowite: koniec $E_{i}$, $(1 \le E_{i} \le N)$, i rury $B1_{i}$, $B2_{i}$, $(2 \le B1_i \le N; 2 \le B2_i \le N)$. Rura $1$ łączy oborę, jej koniec jest odległy o $1$.

Wejście

• Wiersz $1$: całkowite $N$, $C$ rozdzielone spacją.

• Wiersze $2,\ldots,C+1$: wiersz $i+1$ opisuje rozgałęzienie $i$ trzema całkowitymi przez spacje: $E_{i}$, $B1_{i}$, $B2_{i}$.

Wyjście

• Wiersze $1,\ldots,N$: wiersz $i$ zawiera całkowitą odległość końca rury $i$ od obory.

Przykład

Wejście 1

5 2
3 5 4
1 2 3

Wyjście 1

1
2
2
3
3

Uwagi

Wejście opisuje tę mapę:

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

Rura $1$ zawsze jest odległa o $1$. Rury $2$, $3$ łączą się z nią bezpośrednio, odległość $2$. Rury $4$, $5$ łączą się z $3$, odległość $3$.

Autor zadania: Rob Kolstad, 2008