1. 部分問題

グラフ \(G\) が与えられたときの、出力するべき値は以下のようになります。

• 二部グラフでないならば \(-1\)

• 二部グラフのとき

  連結成分ごとには、塗り分け方は（白・黒を反転させた） \(2\) 通りのみである。

  よって、連結成分ごとに頂点の塗り方を一つとれば、\(\min(\) 白 \(,\) 黒 \()\) の総和が答えとなる。

---

2. クエリごとの操作

辺 \((u, v)\) を追加して塗り方が変化するのは「頂点 \(u, v\) が含まれる連結成分」だけですから、その部分だけを計算しなおす事を考えます。

ケース 1 : \(u, v\) が同じ連結成分のとき

• \(u, v\) の色が異なるなら、なにもしない。

• \(u, v\) の色が同じなら、二部グラフでなくなるのでこれ以降 \(-1\) とする。

ケース 2 : \(u, v\) が違う連結成分のとき

二部グラフでなくなることはない。

• \(u, v\) の色が異なるなら、なにもしない。

• \(u, v\) の色が同じなら、どちらかの連結成分の色をすべて反転させる。

そのあと、以降は同じ連結成分として扱うためマージをする。

---

3. マージテクによる高速化

ケース 2 のクエリは高々 \(N\) 回です。 ここで「どちらかの連結成分の色をすべて反転させる」のは、愚直に行うとクエリごとに最悪 \(O(N)\) で全体 \(O(N^2)\) です。

しかし、以下のような工夫で計算量を全体 \(O(N \log N)\) にすることができます。

• 頂点数が少ない方の連結成分を走査（反転）して、大きい方の成分へマージする。

計算量が \(O(N \log N)\) になる理由

ある頂点 \(u\) に注目します。\(u\) が走査されるのは「\(u\) を含む連結成分が自分より大きい連結成分とマージされる」ときだけです。

1. 走査されたとすると、連結成分のサイズは \(2\) 倍以上になる
2. 連結成分のサイズは最大 \(N\) なので、ある頂点について走査は \(\log_2N\) 回しか発生しない
3. すべての頂点で合計しても \(O(N \log N)\) となる

---

4. 実装例

注意しなければいけないのは、各クエリについて「小さい方の連結成分のサイズ」で抑えられるような操作しかしてはいけないことです。（もし TLE するようであれば、ここが壊れていないか確認してください）

以下の実装例では次のようにしています。

• \(u, v\) が同じ連結成分かどうかは uf を用いて判定する

• 連結成分の leader で「白で塗っている頂点集合」・「黒で塗っている頂点集合」を管理する

• set で管理することで「ある頂点がいま何色」で塗られているかを高速に取得できるようにする

計算量は \(O(Q \alpha (N) + N \log N)\) です。

from atcoder.dsu import DSU

n, q = (int(x) for x in input().split())
uf = DSU(n)
c = [[set([i]), set()] for i in range(n)]

ans = 0
for i in range(q):
    u, v = (int(x)-1 for x in input().split())
    if ans == -1:
        print(ans)
        continue
    
    lu = uf.leader(u)
    lv = uf.leader(v)
    f = (u in c[lu][0]) ^ (v in c[lv][0])
    if uf.same(u, v):
        if f == 0:
            ans = -1
    else:
        if uf.size(u) < uf.size(v):
            u, v = v, u
            lu, lv = lv, lu
        
        ans -= min(len(c[lu][0]), len(c[lu][1]))
        ans -= min(len(c[lv][0]), len(c[lv][1]))
        
        c[lu][0] |= c[lv][1^f]
        c[lu][1] |= c[lv][f]
        c[lv] = [set(), set()]
        nl = uf.merge(lu, lv)
        if nl != lu: c[nl] = c[lu]
        
        ans += min(len(c[nl][0]), len(c[nl][1]))
    
    print(ans)