#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
const int N = 2e5+10;
int n, m, q;
int st[2][N], ft[2][N], p[2][18][N];
vi UU[N], DD[N], t[2][N], eul[2];
int dsu[N];
void init() {
for(int i = 0; i < n; i++)
dsu[i] = i;
}
int find(int x) {
if(dsu[x] == x) return x;
return dsu[x] = find(dsu[x]);
}
void dfs(int u, int id) {
st[id][u] = eul[id].size();
eul[id].push_back(u);
for(int v : t[id][u])
dfs(v, id);
ft[id][u] = eul[id].size()-1;
}
set<int> bf;
vi ans;
vi check_validity(int _n, vi X, vi Y, vi S, vi E, vi L, vi R) {
n = _n;
m = X.size();
q = S.size();
for(int i = 0; i < m; i++) {
if(X[i] > Y[i]) swap(X[i], Y[i]);
UU[X[i]].push_back(Y[i]);
DD[Y[i]].push_back(X[i]);
}
memset(p,-1,sizeof p);
init();
for(int i = 0; i < n; i++) {
for(int v : DD[i]) {
int par = find(v);
if(par == i) continue;
t[1][i].push_back(par);
// cout << "low " << i << " --> " << par << endl;
p[1][0][par] = i;
dsu[par] = i;
}
}
init();
for(int i = n-1; i >= 0; i--) {
for(int v : UU[i]) {
int par = find(v);
if(par == i) continue;
t[0][i].push_back(par);
// cout << "big " << i << " --> " << par << endl;
p[0][0][par] = i;
dsu[par] = i;
}
}
dfs(0,0);
dfs(n-1,1);
// for(int i = 0; i < n; i++)
// cout << eul[0][i] << " "; cout << endl;
// for(int i = 0; i < n; i++)
// cout << eul[1][i] << " "; cout << endl;
for(int id : {0,1})
for(int j = 1; j < 18; j++)
for(int i = 0; i < n; i++)
if(p[id][j-1][i] != -1)
p[id][j][i] = p[id][j-1][p[id][j-1][i]];
for(int Q = 0; Q < q; Q++) {
// cout << "Query = " << S[Q] << " ---> " << E[Q] << ",,,, L = " << L[Q] << " R = " << R[Q] << endl;
int U = S[Q], V = E[Q];
for(int j = 17; j >= 0; j--) {
if(p[0][j][U] != -1 && L[Q] <= p[0][j][U]) U = p[0][j][U];
if(p[1][j][V] != -1 && p[1][j][V] <= R[Q]) V = p[1][j][V];
}
// cout << "query union in " << U << " and " << V << "'s subtree\n";
bf.clear();
int found = 0;
for(int i = st[0][U]; i <= ft[0][U]; i++)
bf.insert(eul[0][i]);
for(int i = st[1][V]; i <= ft[1][V]; i++)
if(bf.find(eul[1][i]) != bf.end())
found++;
if(found) ans.push_back(1);
else ans.push_back(0);
}
return ans;
}
