F - Make Bipartite 3 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

頂点に 1 から N までの番号が付いた、N 頂点 0 辺の無向グラフ G があります。

Q 個のクエリが与えられます。i 番目のクエリでは、グラフ G に頂点 u_i と頂点 v_i を結ぶ辺を追加します。

それぞれのクエリを処理した直後のグラフ G において、以下の条件を満たすように G の各頂点を白または黒のどちらか一色で塗ることができるか判定し、可能な場合は黒に塗る頂点の個数としてありうる最小値を求めてください。

  • どの辺についても、両端の頂点が異なる色で塗られている。

制約

  • 2 \le N \le 2 \times 10^5
  • 1 \le Q \le 2 \times 10^5
  • 1 \le u_i \lt v_i \le N
  • (u_i, v_i) \ne (u_j, v_j) \ (i \ne j)
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
u_1 v_1
u_2 v_2
\vdots
u_Q v_Q

出力

Q 行出力せよ。

i 行目には i 番目のクエリを処理した直後のグラフ G について、以下の値を出力せよ。

  • 条件を満たす塗り方が可能な場合、黒に塗る頂点の個数としてありうる最小値
  • 条件を満たす塗り方が不可能な場合、 -1

入力例 1

4 4
1 2
2 3
3 4
1 3

出力例 1

1
1
2
-1

1, 2, 3 番目のクエリを処理した直後については、条件を満たす塗り方が存在します。

例えば、 3 番目のクエリを処理した直後は、頂点 1, 2, 3, 4 をそれぞれ 白 黒 白 黒 と塗ることができます。これより 黒 に塗る頂点の個数が少なく、条件を満たす塗り方は存在しないので 2 を出力してください。

4 番目のクエリを処理した直後は、条件を満たすように塗ることができません。よって -1 を出力してください。

入力例 2

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

出力例 2

1
2
2
3
3
3
3
4
4
4

Score : 500 points

Problem Statement

There is an undirected graph G with N vertices numbered 1 through N and zero edges.

Q queries are given. In the i-th query, an edge connecting vertices u_i and v_i is added to graph G.

Immediately after processing each query, determine whether it is possible to color each vertex of G white or black so that the following condition is satisfied, and if possible, find the minimum possible number of vertices colored black.

  • For every edge, the two endpoints have different colors.

Constraints

  • 2 \le N \le 2 \times 10^5
  • 1 \le Q \le 2 \times 10^5
  • 1 \le u_i \lt v_i \le N
  • (u_i, v_i) \ne (u_j, v_j) \ (i \ne j)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
u_1 v_1
u_2 v_2
\vdots
u_Q v_Q

Output

Output Q lines.

The i-th line should contain the following value for graph G immediately after processing the i-th query.

  • If a valid coloring is possible, the minimum possible number of vertices colored black.
  • If no valid coloring is possible, -1.

Sample Input 1

4 4
1 2
2 3
3 4
1 3

Sample Output 1

1
1
2
-1

Immediately after processing queries 1, 2, 3, a valid coloring exists.

For example, immediately after processing the third query, vertices 1, 2, 3, 4 can be colored white, black, white, black, respectively. No valid coloring with fewer black vertices exists, so output 2.

Immediately after processing the fourth query, no valid coloring exists. Thus, output -1.

Sample Input 2

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

Sample Output 2

1
2
2
3
3
3
3
4
4
4