#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define f first
#define s second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define lb lower_bound
#define ub upper_bound
const int MAXN=200001;
const ll MOD=1e9+7;
const ll INF = 1e9;
vpi edges;
vector<vi> V[2];
vi pre[2];
vi ipre[2];
vi post[2];
vi ord;
vi p[2];
int up[MAXN];
int par(int x){return(up[x]==x)?x:up[x] = par(up[x]);}
int gx;
int N;
void dfs(int x,int pa,int a){
pre[a][x]=gx;
ipre[a][gx]=x;
++gx;
p[a][x] = pa;
for(auto t:V[a][x])if(t!=pa)dfs(t,x,a);
post[a][x]=gx-1;
}
void generate_tree(int a){
for(int i=0;i<N;++i){
up[i]=i;
}
pre[a].resize(N,0);
ipre[a].resize(N,0);
post[a].resize(N,0);
p[a].resize(N,0);
V[a].resize(N);
gx=0;
for(auto i:edges){
if(par(i.f) == par(i.s))continue;
i.s=par(i.s);
assert(up[i.f] == i.f);
V[a][i.f].pb(i.s);
up[i.s]=par(i.f);
}
if(a==0)dfs(N-1,-1,a);
else dfs(1,-1,a);
}
bool B[MAXN];
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) {
N=_N;
for(int i=0;i<SZ(X);++i){
if(Y[i] > X[i])swap(X[i],Y[i]);
edges.pb(X[i],Y[i]);
}
sort(ALL(edges));
for(int i=0;i<N;++i)ord.pb(i);
generate_tree(0);
for(auto &i:edges)swap(i.f,i.s);
sort(ALL(edges));reverse(ALL(edges));
generate_tree(1);
int Q = S.size();
std::vector<int> A(Q);
for (int i = 0; i < Q; ++i) {
A[i] = 0;
}
for(int t=0;t<SZ(S);++t){
int st=S[t];
while(st!=0 && p[1][st] >= L[t]){
st=p[1][st];
}
// cerr<<"As human can go to "<<st<<'\n';
int en=E[t];
while(en!=N-1 && p[0][en] <= R[t]){
en=p[0][en];
}
for(int i=0;i<N;++i){
if(pre[0][i] < pre[0][en] || pre[0][i] > post[0][en])continue;
if(pre[1][i] < pre[1][st] || pre[1][i] > post[1][st])continue;
// cerr<<"Middle ground "<<i<<' '<<t<<'\n';
A[t]=1;
}
// cerr<<"As wolf can go to "<<en<<'\n';
}
return A;
}
