#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi>vpi;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define MAXN 3010
vi V[MAXN];
int N,M,Q,a,b;
bool A[MAXN][2];
int W[MAXN];
int vis[MAXN];
void dfs(int x, int l){
// cout<<"DFS "<<x<<' '<<l<<'\n';
A[x][0]=1;
for (auto v:V[x])if (vis[v] == 0 && v >= l){
vis[v]=1;
dfs(v,l);
}
}
void dfs2(int x, int r){
A[x][1]=1;
for (auto v:V[x])if (vis[v] == 0 && v <= r){
vis[v]=1;
dfs2(v,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) {
Q = SZ(S);M=SZ(X);
for (int i=0;i<M;++i){
a=X[i];b=Y[i];
V[a].pb(b);
V[b].pb(a);
}
vi out(Q,0);
for (int i=0;i<Q;++i){
memset(vis,0,sizeof(vis));
memset(A,0,sizeof(A));
dfs(S[i],L[i]);
memset(vis,0,sizeof(vis));
dfs2(E[i],R[i]);
// for (int i=0;i<N;++i)cout<<A[i][0]<<' ';cout<<'\n';
// for (int i=0;i<N;++i)cout<<A[i][1]<<' ';cout<<'\n';
// cout<<'\n';
for (int x=0;x<N;++x)if (A[x][0] && A[x][1])out[i]=1;
}
return out;
}
