# QOJ

Time Limit: 2 s Memory Limit: 1024 MB Hackable ✓

# # 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 $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.

### 输入格式

• 其中第 $i$ 行包含两个整数 $u_i, v_i$ ($1 \leq u_i \mathbf{<} v_i \leq n$), 描述一条连接顶点 $u_i$ 与 $v_i$ 的边.

### 样例数据

#### 样例 1 输入

3 3
1 2
1 3
2 3

#### 样例 1 输出

1 2

#### 样例 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