#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
struct DSU {
vi e;
DSU(int n) : e(n, -1) {}
int repr(int u) {
while(e[u] >= 0) u = e[u];
return u;
}
void join(int u, int v) {
u = repr(u);
v = repr(v);
if(u == v) return;
if(e[u] >= e[v]) swap(u, v);
e[u] += e[v];
e[v] = u;
}
bool same(int u, int v) {
return repr(u) == repr(v);
}
};
vi check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R) {
int q = (int)S.size(), m = (int)X.size();
vi Re(q, 0);
for(int nr = 0; nr < q; ++nr) {
DSU St(n), Dr(n);
for(int i = 0; i < m; ++i) {
if(X[i] <= R[nr] && Y[i] <= R[nr])
St.join(X[i], Y[i]);
if(X[i] >= L[nr] && Y[i] >= L[nr])
Dr.join(X[i], Y[i]);
}
for(int i = L[nr]; i <= R[nr]; ++i) {
if(Dr.same(i, S[nr]) && St.same(i, E[nr])) Re[nr] = 1;
}
}
return Re;
}
