AT_abc451_f [ABC451F] Make Bipartite 3

頂点に $ 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 $

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