威斯康辛酪農區悶熱潮濕的夏季讓乳牛渴望解渴。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