Problem Statement

You are given a graph $G$ with $N$ vertices and $M$ edges.
For every integer $i$ such that $1 ≦ i ≦ N$, answer the following question.

Question. When you add as many edges as you like ($0$ or more) to the graph $G$, can you make a connected component with $i$ vertices? If so, what is the minimum number of edges to add?

Input

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

Line $1$ contains the integer $N(1 ≦ N ≦ 10^5)$, the number of vertices of the graph, and the integer $M(1 ≦ M ≦ 2×10^5)$, the number of edges, separated by a space. Line $i$ $(1 ≦ i ≦ M)$ of the following $M$ lines contains the numbers $u_i, v_i(1 ≦ u_i, v_i ≦ N)$ of the $2$ vertices connected by the $i$-th edge, separated by a space.
The graph $G$ may contain multiple edges and self-loops.

Output

The output consists of $N$ lines.
On line $i$ $(1 ≦ i ≦ N)$, output the answer to the question for that $i$.
If the answer is "cannot be made", output the integer $-1$.

Sample

6 3
2 3
4 5
5 6

0
0
0
1
1
2

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

-1
0
0
0
1
1
1
-1
2