Les étés moites et brûlants du district laitier du Wisconsin donnent soif aux vaches. Farmer John pompe de l'étable une eau claire et froide dans $N$ tuyaux ramifiés, $(3 \le N \le 99999)$, $N$ impair, numérotés $1,\ldots,N$. La chaleur estivale réchauffe l'eau en circulation. Bessie cherche l'eau la plus froide pour profiter du temps davantage que toute autre vache.

Sa carte complète montre un arbre enraciné à la ferme, dont chaque embranchement a exactement deux tuyaux sortants. Étonnamment, chaque tuyau mesure exactement une unité ; les $N$ tuyaux sont tous reliés d'une manière ou d'une autre à l'arbre.

D'après la carte, listez la distance de l'étable à chaque embranchement et extrémité. Bessie s'en servira pour trouver l'eau la plus froide.

Une extrémité de tuyau mène à un embranchement ou à un robinet et porte le numéro du tuyau. La carte a $C$ connexions, $(1 \le C \le N)$, chacune trois entiers : extrémité $E_{i}$, $(1 \le E_{i} \le N)$, et tuyaux $B1_{i}$, $B2_{i}$, $(2 \le B1_i \le N; 2 \le B2_i \le N)$. Le tuyau $1$ rejoint l'étable ; son extrémité est à distance $1$.

Entrée

• Ligne $1$ : entiers $N$, $C$ séparés par un espace.

• Lignes $2,\ldots,C+1$ : la ligne $i+1$ décrit l'embranchement $i$ par trois entiers séparés par des espaces : $E_{i}$, $B1_{i}$, $B2_{i}$.

Sortie

• Lignes $1,\ldots,N$ : la ligne $i$ donne un entier indiquant la distance de l'étable à l'extrémité du tuyau $i$.

Exemples

Entrée 1

5 2
3 5 4
1 2 3

Sortie 1

1
2
2
3
3

Remarque

Cette entrée décrit la carte suivante :

                    +------+
                    | Étable |
                    +------+
                       | 1
                       *
                    2 / \ 3
                         *
                      4 / \ 5

Le tuyau $1$ est toujours à distance $1$. Les $2$, $3$ le rejoignent directement, distance $2$. Les $4$, $5$ rejoignent le $3$, distance $3$.

Auteur du problème : Rob Kolstad, 2008