#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define F first
#define S second
const int MAXN=2e5+10;
const int inf=1e8;
typedef pair<int,int> pii;
struct vertex{
vertex *l,*r;
int sum;
vertex(int s) : l(nullptr),r(nullptr),sum(s) {}
vertex(vertex *l1,vertex *r1) : l(l1),r(r1),sum(0){
if(l1) sum+=l1->sum;
if(r1) sum+=r1->sum;
}
};
vertex *build(int l,int r){
if(l==r) return new vertex(0);
int m=(l+r)>>1;
return new vertex(build(l,m),build(m+1,r));
}
vertex *updt(vertex *nd,int l,int r,int a){
if(l==r)return new vertex(1);
int m=(l+r)>>1;
if(a<=m)return new vertex(updt(nd->l,l,m,a),nd->r);
return new vertex(nd->l,updt(nd->r,m+1,r,a));
}
int query(vertex *nd,vertex *nd1,int l,int r,int a,int b){
if(l>b || a>r)return 0;
if(a<=l && b>=r)return nd->sum-nd1->sum;
int m=(l+r)>>1;
return query(nd->l,nd1->l,l,m,a,b)+query(nd->r,nd1->r,m+1,r,a,b);
}
int n,pai[MAXN],sbt[MAXN],cur,tin[MAXN],root[MAXN],sub[MAXN],tin1[MAXN],r1[MAXN];
vector<int> g[MAXN],g1[MAXN];
vector<pii> arr;
vertex *roots[MAXN];
int find(int x){
return x==pai[x]?x:pai[x]=find(pai[x]);
}
void dfs(int x,int pr=-1){
for(auto u:g[x]){
if(find(u)==find(x) || u==pr)continue;
dfs(u,x);
u=find(u);
g1[x].pb(u);
pai[u]=x;
}
}
void dfstake(int x=0){
tin[x]=cur++;
sbt[x]=1;
for(auto u:g1[x]) dfstake(u),sbt[x]+=sbt[u];
}
void dfs1(int x,int pr=-1){
for(auto u:g[x]){
if(find(u)==find(x) || u==pr)continue;
dfs1(u,x);
u=find(u);
g1[x].pb(u);
pai[u]=x;
}
}
void dfstake1(int x=n-1){
tin1[x]=cur++;
sub[x]=1;
for(auto u:g1[x]) dfstake1(u),sub[x]+=sub[u];
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R){
n=N;
fall(i,0,sz(X)-1){
if(X[i]>Y[i])swap(X[i],Y[i]);
g[X[i]].pb(Y[i]);
}
fall(i,0,n-1)pai[i]=i;
int q=sz(S);
vector<vector<pii>> arr(n);
fall(i,0,q-1) arr[L[i]].pb({S[i],i});
rfall(i,n-1,0){
dfs(i);
for(auto[u,id]:arr[i]) root[id]=find(u);
}
dfstake();
arr.clear(); arr.resize(n);
fall(i,0,n-1)g[i].clear(),g1[i].clear(),pai[i]=i;
fall(i,0,q-1) arr[R[i]].pb({E[i],i});
fall(i,0,sz(X)-1) g[Y[i]].pb(X[i]);
fall(i,0,n-1){
dfs1(i);
for(auto[u,id]:arr[i]) r1[id]=find(u);
}
cur=0;
dfstake1();
vector<int> ord(n);iota(all(ord),0);
sort(all(ord),[&](int a,int b){
return tin1[a]<tin1[b];
});
roots[0]=build(0,n-1);
fall(i,1,n) roots[i]=updt(roots[i-1],0,n-1,tin[ord[i-1]]);
vector<int> ans(q);
fall(i,0,q-1){
int l=r1[i];
//cout<<l<<" "<<tin[l]<<" "<<sub[l]<<" "<<root[i]<<" "<<tin[root[i]]<<" "<<sbt[root[i]]<<"\n";
if(query(roots[tin1[l]+sub[l]],roots[tin1[l]],0,n-1,tin[root[i]],tin[root[i]]+sbt[root[i]]-1)>0) ans[i]=1;
else ans[i]=0;
}
return ans;
}
