Los veranos húmedos y sofocantes de la zona lechera de Wisconsin hacen que las vacas busquen saciar la sed. Farmer John bombea agua clara y fría desde el establo a $N$ tuberías ramificadas, $(3 \le N \le 99999)$, $N$ impar, numeradas $1,\ldots,N$. El calor calienta el agua al circular. Bessie busca la más fría para disfrutar del tiempo más que cualquier otra vaca.

El mapa de todas las tuberías es un árbol con raíz en la granja y exactamente dos tuberías salientes por bifurcación. Sorprendentemente cada tubería mide una unidad; todas las $N$ se conectan de alguna manera al árbol.

Con el mapa, lista la distancia del establo a cada bifurcación y extremo. Bessie lo usará para hallar el agua más fría.

Cada extremo puede entrar a una bifurcación o ser un grifo, y lleva el número de la tubería. Hay $C$ conexiones, $(1 \le C \le N)$, cada una con tres enteros: extremo $E_{i}$, $(1 \le E_{i} \le N)$, y tuberías $B1_{i}$, $B2_{i}$, $(2 \le B1_i \le N; 2 \le B2_i \le N)$. La $1$ se conecta al establo, y su extremo está a distancia $1$.

Entrada

• Línea $1$: enteros $N$, $C$ separados por espacio.

• Líneas $2,\ldots,C+1$: la línea $i+1$ describe la bifurcación $i$ con tres enteros separados por espacios: $E_{i}$, $B1_{i}$, $B2_{i}$.

Salida

• Líneas $1,\ldots,N$: la línea $i$ contiene la distancia entera del establo al extremo de la tubería $i$.

Ejemplos

Entrada 1

5 2
3 5 4
1 2 3

Salida 1

1
2
2
3
3

Nota

La entrada describe este mapa:

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

La tubería $1$ siempre está a distancia $1$. Las $2$, $3$ se conectan directamente a ella, distancia $2$. Las $4$, $5$ conectan a la $3$, distancia $3$.

Autor del problema: Rob Kolstad, 2008