#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define fi first
#define se second
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> void outvv(T v){for(auto x:v)outv(x);}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
const ll inf=1001001001001001001;
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 Q = S.size();
vvi g(n);
rep(i,X.size()){
g[X[i]].pb(Y[i]);g[Y[i]].pb(X[i]);
}
vi parL(n,-1),parR(n,-1);
vvi queryL(n),queryR(n);
{
vi pp(n,-1);
function<ll(ll)> root=[&](ll i){
if(pp[i]==-1)return i;
pp[i]=root(pp[i]);
return pp[i];
};
vvi tmp(n);
rep(i,Q)tmp[L[i]].pb(i);
for(int i=n-1;i>=0;i--){
for(auto x:g[i])if(x>i){
ll t=root(x);
if(t!=i)parL[t]=pp[t]=i;
}
for(ll x:tmp[i])queryL[root(S[x])].pb(x);
}
}
{
vi pp(n,-1);
function<ll(ll)> root=[&](ll i){
if(pp[i]==-1)return i;
pp[i]=root(pp[i]);
return pp[i];
};
vvi tmp(n);
rep(i,Q)tmp[R[i]].pb(i);
rep(i,n){
for(auto x:g[i])if(x<i){
ll t=root(x);
if(t!=i)parR[t]=pp[t]=i;
}
for(ll x:tmp[i])queryR[root(E[x])].pb(x);
}
}
vvi gL(n),gR(n);
rep(i,n)if(parL[i]!=-1)gL[parL[i]].pb(i);
rep(i,n)if(parR[i]!=-1)gR[parR[i]].pb(i);
ll cnt=0;
vp euler(n);
function<void(ll)> dfs0=[&](ll i){
euler[i].fi=cnt++;
for(ll x:gR[i])dfs0(x);
euler[i].se=cnt;
};dfs0(n-1);
vp rng(Q);
rep(i,n)for(auto x:queryR[i])rng[x]=euler[i];
vector<set<ll>> dp(n);
vector<int> ans(Q);
// for(auto x:rng)cout<<x.fi<<' '<<x.se<<endl;
// for(auto x:euler)cout<<x.fi<<' '<<x.se<<endl;
function<void(ll)> dfs1=[&](ll i){
dp[i].insert(euler[i].fi);
for(ll x:gL[i]){
dfs1(x);
if(dp[i].size()<dp[x].size())swap(dp[i],dp[x]);
for(ll y:dp[x])dp[i].insert(y);
}
for(auto x:queryL[i]){
auto itr=dp[i].lower_bound(rng[x].fi);
if(itr!=dp[i].end()&&*itr<=rng[x].se)ans[x]=1;
}
};dfs1(0);
return ans;
}
