分数: 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