### ZJ g598 另解

首先知道甚麼是二分圖，就是一個圖上可以填兩種顏色，使得每個邊他們兩端的顏色不相同。

題目就是要問是不是二分圖。

先在原本的圖建好顏色，可能有很多個子圖，所以可能很多填法，如分成兩個連通塊: 101/10 和 101/01 都合法，但這沒關係，前面先隨便填一種，然後記得他在哪一塊連通塊(給個編號例如叫 C[i])，接著縮點，把一個連通塊弄成一個點，後面加入新的邊的時候，我們可以用一個 flip 代表有沒有被翻轉 (也就是 0 跟 1 互換)，也就是真的顏色，然後第一個點的 flip 一樣不重要，那後面就分成兩個狀況:
1. 兩個點在同個連通塊: 那就直接判斷顏色
2. 兩個點在不同個連通塊: 如果是第一次走到那就調整 flip 讓它們符合關係，如果不是就判斷 `flip[C[now] xor rb[now], flip[C[next]] xor rb[next]` 的關係 (這裡的 now, next 是原始編號、C[i]是所屬連通塊邊號)

時間複雜度 $O(n+m+pk)$
詳細請參考下方程式和註解:

// Author : rickytsung
// Problem : ZJ g598 AC(71ms)
// Date : 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define i64 long long
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int, int>
#define f first
#define s second
#define pb(x) push_back(x)
using namespace std;
mt19937 rng(114514);
const int mod1 = 998244353;

int rnd(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

i64 gcd(i64 a,i64 b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

i64 lcm(i64 a, i64 b){
    return a/gcd(a, b) * b;
}

const int maxn = 20005;
vector<int> G[maxn];
vector<pair<int, pair<int,int>>> H[maxn]; // from_com to_com (from to)
int rb[maxn], flip[maxn], C[maxn];
// rb -> color c -> component
bool ans = 0;

void dfs1(int now, int com, int col){
    rb[now] = col;
    C[now] = com;
    for(auto &i:G[now]){
        if(rb[i] == -1){
            dfs1(i, com, col^1);
        }
    }
}

void dfs2(int now, int col){
    flip[now] = col;
    
    for(auto &i:H[now]){
        if(flip[i.f] == -1){ // flip not determined
            dfs2(i.f, flip[now]^rb[i.s.f]^rb[i.s.s]^1); // determine other com flip
        }
        else{ // flip determined
            if(flip[now]^rb[i.s.f] == flip[i.f]^rb[i.s.s]){ // no good
                ans = 1;
            }
        }
    }
}
int main() {
    IOS;
    int n, m, u, v, q, k;
    cin >> n >> m;
    while(m--){
        cin >> u >> v;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    memset(rb, -1, sizeof(rb));

    for(int i = 0; i <= n; i++){
        if(rb[i] == -1){
            dfs1(i, i, 0);
        }
    }
    
    cin >> q >> k;
    
    for(int z = 1; z <= q; z++){
        ans = 0;
        vector<int> vis_list;
        for(int i = 0; i < k; i++){
            cin >> u >> v;
            if(C[u] == C[v]){ // in the same component
                if(rb[u] == rb[v]) ans = 1; 
            }
            else{ //not in the same
                vis_list.pb(C[u]); // the node we need to check
                vis_list.pb(C[v]);
                H[C[u]].push_back({C[v], {u,v}}); // compressed graph
                H[C[v]].push_back({C[u], {v,u}});
            }
        }
        
        for(auto &i : vis_list){
            flip[i] = -1; // not vis
        }
        
        for(auto &i : vis_list){
            if(flip[i] == -1){ // not visited -> visit 
                dfs2(i, 0);
            }
        }
        
        for(auto &i : vis_list){
            H[i].clear(); // clear the graph array(used part only so time complexity wont f up)
        }
        
        if(ans) cout << z << '\n';
    }
}