QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Hackable ✓
[+20]

# 61. Cut Cut Cut!

统计

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

For each 2in, 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 (1n105,1m3×105) - 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 ui,vi (1ui<vin) - an edge between the vertex ui and vi.

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 n1 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 条边连接顶点 uivi. 保证 1 号点的出度不超过 20.

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

输入格式

输入的第一行包含两个整数 n,m (1n105,1m3×105), 表示顶点的数量和边的数量.

接下来 m 行描述图 G:

  • 其中第 i 行包含两个整数 ui,vi (1ui<vin), 描述一条连接顶点 uivi 的边.

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

输出格式

输出一行, 包含 n1 个整数, 其中第 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

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