#include "bits/stdc++.h"
#include "werewolf.h"
// #include "grader.cpp"
using namespace std;
#define SZ(s) (int)s.size()
const int N = 2e5 + 5;
vector <int> v[N], h[N], w[N], ph[N], pw[N], p;
int fnd(int x) {
if(p[x] == x) return x;
return p[x] = fnd(p[x]);
}
vector <int> check_validity(int n, vector <int> x, vector <int> y, vector <int> S,
vector <int> E, vector <int> L, vector <int> R) {
int m = SZ(x), q = SZ(S);
for(int i = 0; i < m; i++) {
v[x[i]].push_back(y[i]);
v[y[i]].push_back(x[i]);
}
vector <int> vis(n, 0);
vector <vector <int>> sph(n, vector <int> (25, 0)), spw(n, vector <int> (25, 0));
p.resize(n);
for(int i = 0; i < n; i++) {
p[i] = i, sph[i][0] = i;
}
for(int i = n-1; i >= 0; i--) {
vis[i] = true;
for(auto j : v[i]) {
if(!vis[j]) continue;
int k = fnd(j);
if(k == i) continue;
p[k] = i;
sph[k][0] = i;
h[i].push_back(k);
// h[k].push_back(i);
}
}
vis.assign(n, 0);
for(int i = 0; i < n; i++) {
p[i] = i, spw[i][0] = i;
}
for(int i = 0; i < n; i++) {
vis[i] = true;
for(auto j : v[i]) {
if(!vis[j]) continue;
int k = fnd(j);
if(k == i) continue;
p[k] = i;
spw[k][0] = i;
w[i].push_back(k);
// w[k].push_back(i);
}
}
for(int j = 1; j < 25; j++) {
for(int i = 0; i < n; i++) {
sph[i][j] = sph[sph[i][j-1]][j-1];
spw[i][j] = spw[spw[i][j-1]][j-1];
}
}
vector <int> ans;
for(int i1 = 0; i1 < q; i1++) {
int s = S[i1], e = E[i1], l = L[i1], r = R[i1];
for(int i = 24; i >= 0; i--) {
if(sph[s][i] >= l) s = sph[s][i];
if(spw[e][i] <= r) e = spw[e][i];
}
vis.assign(n, 0);
queue <int> q;
q.push(s);
while(!q.empty()) {
int k = q.front();
q.pop();
vis[k] = true;
for(auto i : h[k]) {
q.push(i);
}
}
q.push(e);
int tr = 0;
while(!q.empty()) {
int k = q.front();
q.pop();
if(vis[k]) tr = 1;
for(auto i : w[k]) {
q.push(i);
}
}
ans.push_back(tr);
}
return ans;
}
