CUBE-224: Lion Army

#include <bits/stdc++.h>

using namespace std;
const int N = 3e5;
const int mod = 1e9 + 7;
int di[N+10];
int parent[2*N+10];
int cnt;

int root(int u){
    if(parent[u] == u) return u;
    return parent[u] = root(parent[u]);
}

void mrg(int u, int v){
    u = root(parent[u]);
    v = root(parent[v]);
    if(u == v) return;
    parent[v] = u;
    cnt --;
}

int main(){

    int n, m;
    scanf("%d%d", &n, &m);
    cnt = 2*n;

    di[0] = 1;
    for(int i=1;i<=n;i++){
        di[i] = di[i-1] * 2;
        di[i] %= mod;
    }

    for(int i=1;i<=2*n;i++)
        parent[i] = i;

    bool check = true;
    for(int i=1;i<=m;i++){
        int opr, a, b;
        scanf("%d%d%d", &opr, &a, &b);
        if(!check){
            printf("0\n");
            continue;
        }
        /// a = Aa, b = Ab
        /// a + n = Ha, b + n = Hb
        if(opr == 1){
            mrg(a, b);
            mrg(a+n, b+n);
        }
        else {
            mrg(a, b+n);
            mrg(a+n, b);
        }
        if(root(a) == root(a + n) or root(b) == root(b + n)) { /// Ha != Aa and Hb != Ab
            check = false;
            printf("0\n");
            continue;
        }
        printf("%d\n", di[cnt/2]);
    }

    return 0;
}