对于当前所有有联系的灯泡我们可以用一个数组表示,如果当前的灯泡是有联系的,比如按下$i$可以影响$j$,我们可以用$a_{ij}$表示出,而$a_{ij}$我们用一个01二进制数表示出,这样就可以判断所有开关之前的联系

那么对于最终状态我们要这么表示呢?我们可以看题目给出的状态和最终的状态是否一致,如果不一致,那就是需要按下(这是由于灯泡只有开和关这两种状态我们一样开以用01表示出)

所以我们可以假设最终状态为final, 初始状态设为state那么对于是否要按下我们有算式state ^ final这个式子代表是否需要按下

那我们可以对当前灯泡是否要按下设为$x_i$这个$x_i$一样是一个01串我们可以对于上述列出方程组

$a_{1,1}*x_1 (xor) a_{1,2}*x_2...=state_1(xor)final_1$

...

$a_{n,1}*x_1(xor)a_{n,2}*x_2...=state_n(xor)final_n$

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

const int N = 35;

int a[N];
int n, T, ans;

int main() {
    cin >> T;
    while(T -- ) {
        cin >> n;
        for(int i = 1; i <= n; i ++ ) cin >> a[i];
        for(int i = 1, j; i <= n; i ++ ) {
            scanf("%d", &j);
            a[i] ^= j;
            a[i] |= 1 << i;
        }
        int x, y;
        while(~scanf("%d%d", &x, &y) && x && y) {
            a[y] |= 1 << x;
        }
        ans = 1;
        for(int i = 1; i <= n; i ++ ) {
            for(int j = i + 1; j <= n; j ++ ) 
                if(a[j] > a[i]) swap(a[j], a[i]);
            if(a[i] == 0) { ans = 1 << (n - i + 1); break; }
            if(a[i] == 1) { ans = 0; break; }
            for(int k = n; k; k -- ) {
                if(a[i] >> k & 1) {
                    for(int j = 1; j <= n; j ++ ) 
                        if(i != j && (a[j] >> k & 1)) a[j] ^= a[i];
                    break;
                }
            }
        }
        if(!ans) puts("Oh,it's impossible~!!");
        else printf("%d\n", ans);
    }
    return 0;
}