1. Subproblem

Given a graph \(G\), the answer to be printed is:

• \(-1\) if it is not bipartite.

• If it is bipartite:

  Each connected component has only two ways of painting (where one is obtained by flipping the other).

  Thus, by taking one painting way for each connected component, the answer is the sum of \(\min(\)white\(,\)black\()\).

---

2. Operation for each query

Adding edge \((u, v)\) only affects to the paintings of the connected components containing vertices \(u\) and \(v\), so we will consider updating only those parts.

Case 1: if \(u\) and \(v\) belong to the same connected component

• If \(u\) and \(v\) have different colors, do nothing.

• If \(u\) and \(v\) have the same color, the graph is no longer bipartite, so the answer is \(-1\) from now on.

Case 2: if \(u\) and \(v\) belong to different connected components

The graph never becomes not bipartite.

• If \(u\) and \(v\) have different colors, do nothing.

• If \(u\) and \(v\) have the same color, flip the colors of all vertices in either connected component.

Afterward, let them belong to the same connected component by merging them.

---

3. Applying merging trick for optimization

Case 2 queries are given at most \(N\) times. However, flipping the color of any one connected component naively costs \(O(N)\) time per query, for a total of \(O(N^2)\) time at worst.

However, the following strategy can reduce the total complexity to \(O(N \log N)\):

• Scan (flip) the connected component with fewer vertices, and merge it into the larger one.

Why does complexity become \(O(N \log N)\)?

Fix a vertex \(u\). Then \(u\) is scanned only when a connected component containing \(u\) is merged into a larger connected component.

1. When scanned, the size of the connected component at least doubles.
2. Since the size of connected component is at most \(N\), a vertex is scanned no more than \(\log_2N\) times.
3. That totals to \(O(N \log N)\) for all vertices.

---

4. Sample code

Note that the cost of any operation performed in a query must be bounded by the size of the smaller connected component. (If you get TLE (Time Limit Exceeded) verdict, recheck that this assumption is not violated.)

In the following sample code, we take the following approach:

• Use a Disjoint Set Union (DSU) to determine if \(u\) and \(v\) belong to the same connected component.

• Let the leader of a connected component manage the vertex sets painted white and black.

• By managing them in a set, the color of any vertex can be retrieved fast.

The time complexity is \(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)