#include "werewolf.h"
#include<bits/stdc++.h>
#define ll int
#define pb push_back
#define ld long double
#define F first
#define S second
#define mp make_pair
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=5e5+500;
const ll inf=1e9+900;
vector<ll> c[2];
bool is_barkh(ll l,ll r,ll L,ll R){
set<ll> st;
for(ll i=l;i<r;i++){
st.insert(c[0][i]);
}
for(ll i=L;i<R;i++){
ll v=c[1][i];
if(st.find(v)!=st.end())return 1;
}
return 0;
}
ll n,m,q;
vector<ll> ger[maxn];
ll par[maxn];
bool hast[maxn];
vector<ll> tree[2][maxn];
ll st[2][maxn];
ll et[2][maxn];
ll tt=0;
ll cnt=-1;
ll findPar(ll x){
if(par[x]==x)return x;
par[x]=findPar(par[x]);
return par[x];
}
void clearr(){
cnt++;
for(ll i=0;i<maxn;i++){
par[i]=i;
hast[i]=0;
}
}
void add(ll x){
hast[x]=1;
for(auto v:ger[x]){
if(hast[v]){
ll r=findPar(v);
if(r!=x){
par[r]=x;
tree[cnt][x].pb(r);
}
}
}
}
void dfs(ll a,ll b){
c[b].pb(a);
st[b][a]=tt++;
for(auto v:tree[b][a]){
dfs(v,b);
}
et[b][a]=tt;
}
vector<ll> li[maxn];
vector<ll> ri[maxn];
ll lp[maxn];
ll rp[maxn];
vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R) {
q = S.size();
m=X.size();
n=N;
for(ll i=0;i<m;i++){
ger[X[i]].pb(Y[i]);
ger[Y[i]].pb(X[i]);
}
for(ll i=0;i<q;i++){
li[L[i]].pb(i);
ri[R[i]].pb(i);
}
clearr();
for(ll i=0;i<n;i++){
add(i);
for(auto x:ri[i]){
rp[x]=findPar(E[x]);
}
}
ll rotr=findPar(0);
clearr();
for(ll i=n-1;i>=0;i--){
add(i);
for(auto x:li[i]){
lp[x]=findPar(S[x]);
}
}
ll rotl=findPar(0);
tt=0;
dfs(rotr,0);
tt=0;
dfs(rotl,1);
vector<int> ans(q);
for(ll i=0;i<q;i++){
ll X=rp[i];
ll Y=lp[i];
ans[i]=is_barkh(st[0][X],et[0][X],st[1][Y],et[1][Y]);
}
for(ll i=0;i<q;i++){
if(S[i]<L[i] || E[i]>R[i])ans[i]=0;
}
return ans;
}
