#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;
int n,pai[MAXN];
vector<int> g[MAXN];
bool ok;
int find(int x){
return x==pai[x]?x:pai[x]=find(pai[x]);
}
void merge(int a,int b){
g[a].pb(b),g[b].pb(a);
a=find(a),b=find(b);
pai[a]=b;
}
void dfs(int x,int p,int target,int l,int r,bool pas){
if(x==target){
ok=1;
return;
}
for(auto u:g[x]){
if(u==p) continue;
if(u<=r && u>=l) dfs(u,x,target,l,r,pas);
else if(x<l && u<l) dfs(u,x,target,l,r,pas);
else if(x<=r && x>=l){
if(u<l && !pas) dfs(u,x,target,l,r,pas);
else if(u>r) dfs(u,x,target,l,r,1);
}
else if(x>r && u>=r) dfs(u,x,target,l,r,pas);
}
}
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;
vector<pii> edges;
fall(i,0,sz(X)-1){
edges.pb({max(X[i],Y[i]),min(X[i],Y[i])});
}
sort(all(edges),[&](pii a,pii b){
if(a.F!=b.F) return a.F<b.F;
return a.S<b.S;
});
fall(i,0,n-1) pai[i]=i;
for(auto [a,b]:edges) if(find(a)!=find(b)){
merge(a,b);
}
vector<int> ans(sz(R));
fall(i,0,sz(L)-1){
ok=0;
dfs(E[i],-1,S[i],L[i],R[i],0);
ans[i]=ok;
}
return ans;
}
