#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
#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 fi first
#define se second
#define pb emplace_back
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> void outvp(T v){rep(i,v.size()){cout<<'('<<v[i].fi<<','<<v[i].se<<')';}cout<<endl;}
template<class T> void outvvp(T v){for(auto x:v)outvp(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){
ll M=X.size(),Q=L.size();
vvi ord(2);
vvp rng(2,vp(Q));
vector<int> ans(Q);
{
vvi edge(N),query(N);
vi par(N,-1),data(N,-1),lca(Q);
rep(i,M)edge[min(X[i],Y[i])].pb(i);
rep(i,Q)query[L[i]].pb(i);
auto root=[&](auto && self, ll i) -> ll {
if(data[i]==-1)return i;
data[i]=self(self,data[i]);
return data[i];
};
for(int i=N-1;i>=0;i--){
for(ll x:edge[i]){
ll a=root(root,X[x]),b=root(root,Y[x]);
if(a!=b){
if(a<b)swap(a,b);
par[a]=data[a]=b;
}
}
for(ll x:query[i]){
lca[x]=root(root,S[x]);
}
}
vvi ch(N);
rep(i,N)if(par[i]!=-1)ch[par[i]].pb(i);
ll cnt=0;
vp euler(N);
auto dfs=[&](auto && self, ll i) -> void {
ord[0].pb(i);
euler[i].fi=cnt++;
for(ll x:ch[i])self(self,x);
euler[i].se=cnt;
};dfs(dfs,0);
rep(i,Q)rng[0][i]=euler[lca[i]];
}
{
vvi edge(N),query(N);
vi par(N,-1),data(N,-1),lca(Q);
rep(i,M)edge[max(X[i],Y[i])].pb(i);
rep(i,Q)query[R[i]].pb(i);
auto root=[&](auto && self, ll i) -> ll {
if(data[i]==-1)return i;
data[i]=self(self,data[i]);
return data[i];
};
rep(i,N){
for(ll x:edge[i]){
ll a=root(root,X[x]),b=root(root,Y[x]);
if(a!=b){
if(a>b)swap(a,b);
par[a]=data[a]=b;
}
}
for(ll x:query[i]){
lca[x]=root(root,E[x]);
}
}
vvi ch(N);
rep(i,N)if(par[i]!=-1)ch[par[i]].pb(i);
ll cnt=0;
vp euler(N);
auto dfs=[&](auto && self, ll i) -> void {
ord[1].pb(i);
euler[i].fi=cnt++;
for(ll x:ch[i])self(self,x);
euler[i].se=cnt;
};dfs(dfs,N-1);
rep(i,Q)rng[1][i]=euler[lca[i]];
}
rep(i,Q){
vi cnt(N);
REP(j,rng[0][i].fi,rng[0][i].se)cnt[ord[0][j]]=1;
REP(j,rng[1][i].fi,rng[1][i].se)if(cnt[ord[1][j]])ans[i]=1;
}
return ans;
}
