QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100

#61. Cut Cut Cut!

Statistics

You are given a directed acyclic graph $G=(V,E)$ with $n$ vertices and $m$ edges. The $i$-th edge is connected from vertex $u_i$ to vertex $v_i$. After a long observation, you find that the outdegree $1$ does not exceed $20$.

For each $2 \leq i \leq n$, you want to know the minimum number of edges you need to delete, so that there is no path between the vertex $1$ and the vertex $i$ that does not pass through the edge you deleted.

Input

The first line contains two integers $n$ and $m$ $(1 \leq n \leq 10^5, 1 \leq m \leq 3 \times 10^5)$ - the number of the vertices and the number of the edges.

The next $m$ lines describes the graph $G$:

  • The $i$-th line of these lines contains two integers $u_i, v_i$ ($1 \leq u_i \mathbf{<} v_i \leq n$) - an edge between the vertex $u_i$ and $v_i$.

It is guaranteed that there are no multiple edges in the graph, and there are no more than $20$ edges satisfy that their starting vertex is vertex $1$.

Output

Output a single line contains $n - 1$ integers - the $i$-th of them describes the minimum number of edges you have to delete.

Examples

Input 1

3 3
1 2
1 3
2 3

Output 1

1 2

Explanation 1

For $i = 2$, the optimal solution is to delete edge $(1, 2)$.

For $i = 3$, the optimal solution is to delete edge $(1, 2)$ and $(1, 3)$.

Input 2

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

Output 2

1 1 1 2 1 0 0

Input 3 / Output 3

You can find them in the additional files.

Input 4 / Output 4

You can find them in the additional files.

给定一张 $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

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