Los veranos húmedos, abrazadores del distrito lechero de Winsconsin estimulan a las vacas a aplacar su sed. El Granjero Juan bombea agua fría en un conjunto de ~N (3 \leq N \leq 99999)~ (~N~ impar) tuberías convenientemente numeradas ~1...N~ desde un pozo ubicado en la granja. Como el agua fluye a través de las tuberías, el calor del verano las calienta. Bessie quiere encontrar el agua más fría de manera que ella pueda disfrutar del clima más que cualquier otra vaca. Ella ha hecho un plano de todo el conjunto de tuberías y se ha dado cuenta que ellas forman un árbol con su raíz en la granja y aun más que cada punto de ramificación tiene exactamente dos tuberías que salen de él. Sorprendentemente, cada tubería tiene una unidad de longitud; por supuesto todas la ~N~ tuberías se conectan de una manera u otra al árbol de tuberías. Dado el plano de todas las conexiones de la tubería, haga una lista de las distancias desde el establo a cada punto de ramificación y a cada punto final. Bessie usará esta lista para encontrar el agua más fría. El extremo de una tubería, el cual podría ser una ramificación o podría ser un grifo, se nombra por el número de la tubería. El plano contiene ~C (1 \leq C \leq N)~ conexiones, cada una de las cuales especifica tres enteros: el punto extremo ~E_i (1 \leq E_i \leq N)~ de una tubería y dos tuberías ramificantes ~B1_i~ y ~B2_i (2 \leq B1_i \leq N; 2 \leq B2_i \leq N)~. La tubería número 1 se conecta al establo; la distancia de su punto extremo al establo es 1.

Entrada

• Línea 1: Dos enteros separados por espacio: ~N~ y ~C~.

• Líneas 2…C+1: La línea ~i+1~ describe el punto de ramificación ~i~ con tres enteros separados por espacio: ~E_i, B1_i,~ y ~B2_i~.

Ejemplo de Entrada

5 2
3 5 4
1 2 3

Salida

• Líneas 1…N: La línea ~i~ de la salida contiene un solo entero que es la distancia desde el establo al punto extremo de la tubería ~i~.

Ejemplo de Salida

1
2
2
3
3

Detalles de la Salida

La tubería 1 está siempre a distancia 1 del establo. Las tuberías 2 y 3 se conectan directamente a la tubería 1 y por lo tanto están a distancia 2 del establo. Las tuberías 4 y 5, las cuales se conectan a la tubería 3, están a distancia 3 del establo.