#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
struct SegmentTree{
int n;
vector<vector<int>> t;
void init(int _n){
n=_n;
t.assign(4*n+1, {});
}
void build(int k, int l, int r, const vector<int> &a){
if (l==r){
t[k].push_back(a[l]);
return;
}
int mid=(l+r)>>1;
build(k<<1, l, mid, a);
build(k<<1|1, mid+1, r, a);
t[k].resize(t[k<<1].size()+t[k<<1|1].size());
merge(t[k<<1].begin(), t[k<<1].end(), t[k<<1|1].begin(), t[k<<1|1].end(), t[k].begin());
}
bool get(int k, int l, int r, int L, int R, int x, int y){
if (r<L || R<l) return 0;
if (L<=l && r<=R){
return upper_bound(t[k].begin(), t[k].end(), y)!=lower_bound(t[k].begin(), t[k].end(), x);
}
int mid=(l+r)>>1;
return get(k<<1, l, mid, L, R, x, y) || get(k<<1|1, mid+1, r, L, R, x, y);
}
} st;
const int N=2e5+10, LG=18;
struct DSU{
int n;
vector<int> lab;
vector<int> g[N];
int tin[N], tout[N], tdfs;
int up[LG][N];
void init(int _n, int root){
n=_n;
lab.assign(n+1, -1);
memset(tin, 0, sizeof tin);
memset(tout, 0, sizeof tout);
tdfs=-1;
up[0][root]=root;
}
int find_set(int u){
return lab[u]<0?u:lab[u]=find_set(lab[u]);
}
void union_sets(int u, int v){
v=find_set(v);
if (v!=u){
up[0][v]=u;
g[u].push_back(v);
lab[u]+=lab[v];
lab[v]=u;
}
}
void dfs(int u){
for (int k=1; k<LG; ++k) up[k][u]=up[k-1][up[k-1][u]];
tin[u]=++tdfs;
for (int v:g[u]) dfs(v);
tout[u]=tdfs;
}
} dsu1, dsu2;
vector<int> g[N];
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=X.size();
for (int i=0; i<M; ++i) g[X[i]].push_back(Y[i]), g[Y[i]].push_back(X[i]);
int Q=S.size();
dsu1.init(N, 0);
for (int i=N-1; i>=0; --i){
for (int j:g[i]) if (j>i) dsu1.union_sets(i, j);
}
dsu2.init(N, N-1);
for (int i=0; i<N; ++i){
for (int j:g[i]) if (j<i) dsu2.union_sets(i, j);
}
dsu1.dfs(0);
dsu2.dfs(N-1);
st.init(N);
vector<int> a(N);
for (int i=0; i<N; ++i) a[dsu2.tin[i]]=dsu1.tin[i];
st.build(1, 0, N-1, a);
vector<int> ans(Q);
for (int i=0; i<Q; ++i){
for (int j=LG-1; j>=0; --j) if (dsu1.up[j][S[i]]>=L[i]) S[i]=dsu1.up[j][S[i]];
for (int j=LG-1; j>=0; --j) if (dsu2.up[j][E[i]]<=R[i]) E[i]=dsu2.up[j][E[i]];
ans[i]=st.get(1, 0, N-1, dsu2.tin[E[i]], dsu2.tout[E[i]], dsu1.tin[S[i]], dsu1.tout[S[i]]);
}
return ans;
}
