Problem Statement

There is a simple undirected graph with $N$ vertices and $M$ edges, whose vertices are numbered $1$ to $N$ and whose edges are numbered $1$ to $M$. For $i = 1, 2, \dots, M$, the $i$-th edge connects vertices $u_i$ and $v_i$.

At time $0$, vertex $1$ is painted black and all other vertices are painted white. Also, at each time $i = 1,2,\dots, N$, the following event occurs.

• Event: Perform operations $1, 2, 3$ in this order.
1. Repaint red every vertex that is painted white and has an adjacent vertex painted black.
2. Repaint white every vertex painted black.
3. Repaint black every vertex painted red.

For each $i = 1, 2, \dots, N$, output the number of vertices painted black immediately after the event at time $i$ occurs.

Input

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

Constraints

• $2 \le N \le 2 \times 10^5$
• $1 \le M \le \min \left( 2 \times 10^5, \frac{N(N-1)}{2} \right)$
• $1 \le u_i < v_i \le N$
• $(u_i, v_i) \neq (u_j, v_j) \quad (i \neq j)$
• All input values are integers.

Output

Output $N$ lines. On the $x$-th line, output the answer for $i = x$.

Sample

6 6
1 4
2 3
2 4
4 5
1 5
2 6

2
2
4
2
4
2

3 1
1 2

1
1
1

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

2
2
3
5
3
5
3
5
3
5