CUBE-T224: Lion Army

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

const int MOD = 1e9 + 7;
const int N = 3e5;
const int logN = log2(N);

int dp[logN + 1], ds[N + 1], sz[N + 1];
bool isWith[N + 1];

int powerOf2(int x){
    int ans = 1;
    for(int i = logN; i >= 0; --i){
        if(x >= (1 << i)){
            ans = (lli)ans * dp[i] % MOD;
            x -= (1 << i);
        }
    }
    return ans;
}

bool fusion(bool a, bool b){
    return ((int)a + (int)b) % 2 == 0;
}

int dsFind(int u){
    if(ds[u] == u){
        return u;
    }
    int p = dsFind(ds[u]);
    isWith[u] = fusion(isWith[u], isWith[ds[u]]);
    return ds[u] = p;
}

int main(){

    dp[0] = 2;
    for(int i = 1; i <= logN; ++i){
        dp[i] = (lli)dp[i - 1] * dp[i - 1] % MOD;
    }

    int nLion, Q;
    scanf("%d%d", &nLion, &Q);
    // DSU Setup
    for(int i = 1; i <= nLion; ++i){
        ds[i] = i;
        sz[i] = 1;
        isWith[i] = true;
    }
    int setCnt = nLion;
    bool conflict = false;
    while(Q--){
        int u, v;
        bool with;
        scanf("%d%d%d", &with, &u, &v);
        if(conflict){
            cout << "0\n";
            continue;
        }
        if(dsFind(u) == dsFind(v)){ // Check Confilct
            if(isWith[u] == isWith[v] && !with || isWith[u] != isWith[v] && with){
                conflict = true;
            }
        } else { // Union
            int headU = dsFind(u);
            int headV = dsFind(v);
            if(sz[headV] > sz[headU]){
                swap(headU, headV);
                swap(u, v);
            }
            ds[headV] = headU;
            sz[headU] += sz[headV];
            isWith[headV] = fusion(fusion(isWith[u], isWith[v]), with);
            --setCnt;
        }
        if(conflict){
            cout << "0\n";
        } else {
            cout << powerOf2(setCnt) << '\n';
        }
    }

    return 0;
}