#include "werewolf.h"
#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
using namespace std;
#define dbg(x) cerr<<#x<<": "<<x<<"\n";
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) {
vector<vector<int>>g(N);
for(int i=0 ; i<(int)X.size() ; i++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
vector<int>ans((int)L.size());
for(int i=0 ; i<(int)L.size() ; i++){
queue<int>bfs;
vector<bool>vis(N);
bfs.push(S[i]);
vis[S[i]]=1;
while(!bfs.empty()){
int u=bfs.front();
bfs.pop();
for(int v:g[u]){
if(v>=L[i] && !vis[v]){
vis[v]=1;
bfs.push(v);
}
}
}
// for(bool x:vis) dbg(x)
bfs.push(E[i]);
vector<bool>vis1(N);
vis1[E[i]]=1;
bool ok=0;
while(!bfs.empty()){
int u=bfs.front();
bfs.pop();
for(int v:g[u]){
if(v<=R[i]){
if(v>=L[i] && vis[v]==1) ok=1;
else if(vis1[v]==1) continue;
vis1[v]=1;
bfs.push(v);
}
if(ok) break;
}
if(ok) break;
}
ans[i]=(ok?1:0);
}
return ans;
}
