威斯康星奶业区闷热潮湿的夏季让奶牛渴望解渴。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