Wisconsins schwüle, drückend heiße Sommer im Milchgebiet machen die Kühe durstig. Farmer John pumpt vom Stall klares kaltes Wasser in $N$ verzweigte Rohre, $(3 \le N \le 99999)$, $N$ ungerade, nummeriert $1,\ldots,N$. Die Sommerhitze erwärmt das fließende Wasser. Bessie sucht das kälteste, um das Wetter mehr als jede andere Kuh zu genießen.

Ihre vollständige Karte bildet einen Baum mit Wurzel auf der Farm, jede Verzweigung hat genau zwei ausgehende Rohre. Erstaunlicherweise ist jedes Rohr genau eine Einheit lang; alle $N$ sind irgendwie mit dem Rohrbaum verbunden.

Liste anhand der Karte die Stallentfernungen aller Verzweigungen und Endpunkte. Bessie nutzt sie zur Suche nach dem kältesten Wasser.

Ein Rohrende führt in eine Verzweigung oder ist ein Wasserhahn und trägt die Rohrnummer. Die Karte hat $C$ Verbindungen, $(1 \le C \le N)$, je drei ganze Zahlen: Endpunkt $E_{i}$, $(1 \le E_{i} \le N)$, und Rohre $B1_{i}$, $B2_{i}$, $(2 \le B1_i \le N; 2 \le B2_i \le N)$. Rohr $1$ führt zum Stall, sein Ende hat Entfernung $1$.

Eingabe

• Zeile $1$: durch Leerzeichen getrennte ganze Zahlen $N$, $C$.

• Zeilen $2,\ldots,C+1$: Zeile $i+1$ beschreibt Verzweigung $i$ mit drei ganzen Zahlen durch Leerzeichen: $E_{i}$, $B1_{i}$, $B2_{i}$.

Ausgabe

• Zeilen $1,\ldots,N$: Zeile $i$ enthält die ganzzahlige Entfernung vom Stall zum Ende von Rohr $i$.

Beispiele

Eingabe 1

5 2
3 5 4
1 2 3

Ausgabe 1

1
2
2
3
3

Hinweis

Diese Eingabe beschreibt folgende Karte:

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

Rohr $1$ hat immer Entfernung $1$. Rohre $2$, $3$ schließen direkt daran an, Entfernung $2$. Rohre $4$, $5$ schließen an Rohr $3$ an, Entfernung $3$.

Aufgabenautor: Rob Kolstad, 2008