ウィスコンシンの酪農地域の蒸し暑い夏は牛を渇かせます。Farmer John は牛舎のポンプから $N$ 本の分岐管へ澄んだ冷水を送ります。$(3 \le N \le 99999)$、$N$ は奇数、番号は $1,\ldots,N$ です。流れるうち夏の熱で水が温まります。Bessie は最も冷たい水を探し、他のどの牛より天気を楽しみたいのです。

全管の地図を作ると、農場を根とする木で各分岐点からちょうど二本の管が出ます。驚くことに各管の長さはちょうど一単位で、もちろん全 $N$ 本が何らかの形で木につながっています。

接続図から全分岐点と端点の牛舎からの距離を列挙してください。Bessie は最も冷たい水探しに使います。

管の端点は分岐点につながるか蛇口で、管番号で呼びます。地図には $C$ 接続、$(1 \le C \le N)$。各接続は三整数：端点 $E_{i}$、$(1 \le E_{i} \le N)$、と分岐管 $B1_{i}$、$B2_{i}$、$(2 \le B1_i \le N; 2 \le B2_i \le N)$。管 $1$ は牛舎につながり、その端点までの距離は $1$。

入力

• 行 $1$：空白区切りの整数 $N$、$C$。

• 行 $2,\ldots,C+1$：行 $i+1$ は空白区切りの三整数 $E_{i}$、$B1_{i}$、$B2_{i}$ で分岐点 $i$ を表します。

出力

• 行 $1,\ldots,N$：行 $i$ の整数は管 $i$ の端点までの牛舎からの距離。

入出力例

入力 1

5 2
3 5 4
1 2 3

出力 1

1
2
2
3
3

注記

上の入力は次の管の地図です。

                    +------+
                    | 牛舎 |
                    +------+
                       | 1
                       *
                    2 / \ 3
                         *
                      4 / \ 5

管 $1$ は常に距離 $1$。管 $2$、$3$ は管 $1$ に直結し距離 $2$。管 $4$、$5$ は管 $3$ につながり距離 $3$。

問題作成者：Rob Kolstad、2008