#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
std::vector<int> check_validity(int n, std::vector<int> x, std::vector<int> y,std::vector<int> st, std::vector<int> e,
std::vector<int> l, std::vector<int> r)
{
int q = st.size();
vector<int> ans(q,0);
vector<int> a[n];
int m = x.size();
for(int i=0;i<m;i++)
{
int u = x[i],v = y[i];
a[u].push_back(v);
a[v].push_back(u);
}
for(int i=0;i<q;i++)
{
vector<int> h(n,0),w(n,0);
for(int s=0;s<n;s++)
{
if(s<=r[i]) h[s]=1;
if(s>=l[i]) w[s]=1;
}
queue<array<int,2>> q;
int s = st[i];
vector<array<int,2>> vis(n,{0,0});
if(h[s]) q.push({{0,s}});
if(w[s] && h[s])q.push({1,s});
while(q.size())
{
int c = q.front()[0],s = q.front()[1];
q.pop();
vis[s][c]=1;
assert((c==0 && h[s]==1) || (c==1 && w[s]==1));
for(int x:a[s])
{
if(c==0)
{
if(h[x]&& w[x]&& vis[x][1]==0)
{
vis[x][1] = 1;
q.push({1,x});
}
if(h[x]&& vis[x][0]==0)
{
vis[x][0] = 1;
q.push({0,x});
}
}
else
{
if(w[x]&& vis[x][1]==0)
{
vis[x][1] = 1;
q.push({1,x});
}
}
}
}
if(vis[e[i]][1])
ans[i]=1;
}
return ans;
}
