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.