#include "werewolf.h"
#include <iostream>
#include <numeric>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#ifdef dremix
#define p(x) cerr<<#x<<" = "<<x<<endl;
#define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
#define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
#define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
#define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
#define p(x) {}
#define p2(x,y) {}
#define pp(x) {}
#define pv(x) {}
#define ppv(x) {}
#endif
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);
const int maxp = 22;
const ld EPS = 1e-18;
const ll INF = 2e18;
const int MOD = 1e9+7;
//const int N = 3e5+1;
vector<int> par,siz,vis;
int find(int x){
return (par[x] == x) ? x : par[x] = find(par[x]);
}
void join(int x, int y){
x = find(x);
y = find(y);
if(x==y)return;
if(siz[y] > siz[x])
swap(x,y);
par[y] = x;
siz[x] += siz[y];
}
vector<vector<int> > a;
int use;
bool flag;
int l,r;
void dfs(int s){
vis[s] = use;
for(auto x : a[s]){
if(use == 1 && x < l)continue;
if(use == 2 && x > r)continue;
if(!vis[x])dfs(x);
if(vis[x] == 1 && use == 2){
flag = true;
}
}
}
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) {
par.resize(N);
siz.resize(N);
vis.resize(N);
a.assign(N,vector<int>());
int q = S.size();
int m = X.size();
int i,k;
for(i=0;i<m;i++){
int x = X[i], y = Y[i];
a[x].push_back(y);
a[y].push_back(x);
}
vector<int> ans;
for(k=0;k<q;k++){
int s = S[k], e = E[k];
l = L[k];
r = R[k];
iota(all(par),0);
fill(all(siz),1);
fill(all(vis),0);
use = 1;
flag = false;
dfs(s);
use = 2;
if(vis[e] == 1)flag = true;
dfs(e);
ans.push_back(flag);
}
return ans;
}
