#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<int> vis1;
vector<int> vis2;
void dfs1(int u, int l){
vis1[u]=1;
for(auto v:adj[u]){
if(vis1[v]==0 and v>=l)dfs1(v,l);
}
}
void dfs2(int u, int r){
vis2[u]=1;
for(auto v:adj[u]){
if(vis2[v]==0 and v<=r)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) {
int q = S.size();
int m=X.size();
int n=N;
adj.resize(n);
for(int i=0;i<m;i++){
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
vector<int> a(q);
vis1.resize(n);
vis2.resize(n);
for(int i=0;i<q;i++){
for(int j=0;j<n;j++){
vis1[j]=0;
vis2[j]=0;
}
dfs1(S[i],L[i]);dfs2(E[i],R[i]);
for(int j=0;j<n;j++){
if(vis1[j]+vis2[j]==2)a[i]=1;
}
}
return a;
}
