#include "werewolf.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=2e5+5;
vector<int> g[N];
int col[N];
vector<int> used;
void dfs(int x, int c, vector<int> &used){
used[x]=1;
//cout<<x<<' '<<c<<' '<<col[x]<<endl;
for(auto it: g[x]){
if(used[it]) continue;
if(c==1 && col[it]<=1)
dfs(it,c,used);
if(c==2 && col[it]>=1)
dfs(it,c,used);
}
}
vector<int> check_validity(int n, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
int m=X.size(),q=S.size();
for(int i=0;i<m;i++){
g[X[i]].pb(Y[i]);
g[Y[i]].pb(X[i]);
}
//Subtask 2
vector<int> ans(q);
for(int i=0;i<q;i++){
if(E[i]>R[i] || S[i]<L[i]) continue;
for(int j=0;j<n;j++){
if(j<L[i]) col[j]=2;
else if(j<=R[i]) col[j]=1;
else col[j]=0;
}
vector<int> a(n),b(n);
dfs(S[i],1,a);
dfs(E[i],2,b);
for(int j=L[i];j<=R[i];j++)
if(a[j] && b[j])
ans[i]=1;
}
return ans;
}
