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 2≤i≤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≤n≤105,1≤m≤3×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 (1≤ui<vi≤n) - 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 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.