题目详情题解（0）讨论（0）提交记录（0）

AT_abc451_f.[ABC451F] Make Bipartite 3

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

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

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

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

输入格式

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

$ 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

  • 输入#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

说明/提示

Sample Explanation 1

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

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

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

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) $
  • 入力される値は全て整数

输入解题思路，AI测评打分。不知道怎么写?

首页