给定一张 $n$ 个点 $m$ 条边的有向无环图 $G=(V,E)$. 第 $i$ 条边连接顶点 $u_i$ 与 $v_i$. 保证 $1$ 号点的出度不超过 $20$.

对每个 $2 \leq i \leq n$, 你想要知道你需要最少删除多少条边, 才能使得不能存在任何一条从 $1$ 到 $i$ 的路径, 使得这条路径不经过任何你删除的边.

输入格式

输入的第一行包含两个整数 $n,m$ ($1 \leq n \leq 10^5, 1 \leq m \leq 3 \times 10^5$), 表示顶点的数量和边的数量.

接下来 $m$ 行描述图 $G$:

• 其中第 $i$ 行包含两个整数 $u_i, v_i$ ($1 \leq u_i \mathbf{<} v_i \leq n$), 描述一条连接顶点 $u_i$ 与 $v_i$ 的边.

保证图中不含有重边, 且以 $1$ 号点为起点的边的数量不超过 $20$ 条.

输出格式

输出一行, 包含 $n-1$ 个整数, 其中第 $i$ 个整数描述你最少需要删除多少条边.

样例数据

样例 1 输入

3 3
1 2
1 3
2 3

样例 1 输出

1 2

样例 1 解释

对于 $i = 2$, 最优的方案是删除边 $(1, 2)$.

对于 $i = 3$, 最优的方案是删除边 $(1, 2)$ 和 $(1, 3)$.

样例 2 输入

8 8
1 2
1 3
1 5
2 4
2 5
3 6
4 5
7 8

样例 2 输出

1 1 1 2 1 0 0

样例 3

你可以在附加文件中找到该样例.

样例 4

你可以在附加文件中找到该样例.