给定一张 $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
你可以在附加文件中找到该样例.