← 返回题目列表

AtCoder · abc451_f

I. 制作二分 3

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有一个无向图 G 与 N 顶点编号 1 通过 N 和零边缘。 给出了

Q 查询。在 i第一个查询,连接顶点的边 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- 第行应包含以下图形值 G 处理后立即 i- 第一个查询。

  • 如果可以进行有效着色,则将顶点着色为黑色的最小可能数量。
  • 如果无法进行有效着色, -1.

样本输入 1

4 4
1 2
2 3
3 4
1 3

示例输出 1

1
1
2
-1

处理查询后立即 1, 2, 3,存在有效的着色。

例如,在处理第三个查询后,顶点立即 1, 2, 3, 4 可以着色 分别是 white, black, white, black。更少的颜色没有有效的着色 black 顶点存在,因此输出 2.

处理第四个查询后,立即不存在有效的着色。因此,输出 -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