#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> con[200005];
int poz[200005];
pair<int,int> forL[400005],forR[400005];
vector<int> withL[400005],withR[400005];
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) {
for(int i=0;i<L.size();i++)
{
withL[L[i]].push_back(i);
withR[R[i]].push_back(i);
}
for(int i=0;i<X.size();i++)
{
con[X[i]].push_back(Y[i]);
con[Y[i]].push_back(X[i]);
}
int cap=-1;
for(int i=0;i<N;i++)
if((int)con[i].size()<=1)
cap = i;
vector<int> lant;
lant.push_back(cap);
for(int i=1;i<N;i++)
{
if(i-2>=0 && con[lant[i-1]][0] == lant[i-2])
lant.push_back(con[lant[i-1]][1]);
else
lant.push_back(con[lant[i-1]][0]);
}
assert((int)lant.size()==N);
for(int i=0;i<N;i++)
poz[lant[i]]=i;
set<int> rele;
for(int i=0;i<N;i++)
rele.insert(poz[i]);
rele.insert(-1);
rele.insert(N);
for(int i=N-1;i>=0;i--)
{
rele.erase(poz[i]);
for(int id:withL[i])
{
forL[id].second = *rele.lower_bound(poz[S[id]]);
forL[id].first = *prev(rele.lower_bound(poz[S[id]]));
forL[id].second--;
forL[id].first++;
}
}
rele.clear();
for(int i=0;i<N;i++)
rele.insert(poz[i]);
rele.insert(-1);
rele.insert(N);
for(int i=0;i<N;i++)
{
rele.erase(poz[i]);
for(int id:withR[i])
{
forR[id].second = *rele.lower_bound(poz[E[id]]);
forR[id].first = *prev(rele.lower_bound(poz[E[id]]));
forR[id].second--;
forR[id].first++;
}
}
vector<int> sol;
for(int i=0;i<S.size();i++)
{
if(poz[S[i]] < poz[E[i]])
{
if(forL[i].second >= forR[i].first)
sol.push_back(1);
else
sol.push_back(0);
}
else
{
if(forR[i].second >= forL[i].first)
sol.push_back(1);
else
sol.push_back(0);
}
}
return sol;
}
