#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()
const int MAXN=2e5+10;
int n;
vector<int> g[MAXN];
bool mark[MAXN][2];
void dfs(int x,int l){
mark[x][1]=1;
for(auto u:g[x]){
if(mark[u][1] || u<l) continue;
dfs(u,l);
}
}
void dfs1(int x,int l,int r){
mark[x][0]=1;
if(x>=l && !mark[x][1]) dfs(x,l);
for(auto u:g[x]){
if(mark[u][0]) continue;
if(u<=r) dfs1(u,l,r);
}
}
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){
g[X[i]].pb(Y[i]);
g[Y[i]].pb(X[i]);
}
vector<int> ans(sz(R));
fall(j,0,sz(S)-1){
fall(i,0,n-1) mark[i][0]=mark[i][1]=0;
dfs1(E[j],L[j],R[j]);
ans[j]=mark[S[j]][1];
}
return ans;
}
