AT_abc451_f [ABC451F] Make Bipartite 3

有一个无向图 $ G $，它有 $ N $ 个顶点和 $ 0 $ 条边，顶点的编号从 $ 1 $ 到 $ N $。 给定 $ Q $ 个查询。在第 $ i $ 个查询中，向图 $ G $ 中添加一条连接顶点 $ u_i $ 和顶点 $ v_i $ 的边。 在处理完每个查询后的图 $ G $ 中，请判断是否可以将 $ G $ 的每个顶点涂成白色或黑色中的一种颜色，且满足以下条件；如果可行，则求出被涂成黑色的顶点数的最小可能值。 - 对于每一条边，其两端的顶点都被涂上了不同的颜色。

输入以以下形式从标准输入中给出。 > $ N $ $ Q $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \cdots $ $ u_Q $ $ v_Q $。

请输出 $ Q $ 行。 在第 $ i $ 行中，输出处理完第 $ i $ 个查询后的图 $ G $ 的以下数值。 - 如果存在满足条件的涂色方式，则输出黑色顶点的最小可能数量。 - 如果不存在满足条件的涂色方式，则输出 $ -1 $。

### 示例说明 1 在处理完第 $1$、$2$、$3$ 个查询后，仍存在满足条件的涂色方式。 例如，在处理完第 $ 3 $ 个查询后，可以将顶点 $ 1, 2, 3, 4 $ 分别涂成 `白`、`黑`、`白`、`黑`。此时被涂成 `黑` 的顶点数量较少，不存在满足条件的涂色方案，因此应输出 $ 2 $。 在处理完第 $4$ 个查询后，无法满足条件地进行涂色。因此，请输出 $-1$。 ### 限制条件 - $ 2 \le N \le 2 \times 10^5 $。 - $ 1 \le Q \le 2 \times 10^5 $。 - $ 1 \le u_i < v_i \le N $。 - $ (u_i, v_i) \ne (u_j, v_j) \ (i \ne j) $。 - 所有输入的值均为整数。