#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;
const int MAXL = 18;
vpi edges;
vector<vi> V[2];
vi pre[2];
vi ipre[2];
vi post[2];
vi ord;
int p[MAXN][MAXL][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[x][0][a] = pa;
for(int i=1;i<MAXL;++i){
if(p[x][i-1][a] == -1)continue;
int b=p[x][i-1][a];
p[x][i][a] = p[b][i-1][a];
}
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);
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);
if(a==0)assert(i.f>i.s);
else assert(i.f<i.s);
V[a][i.f].pb(i.s);
up[i.s]=par(i.f);
}
if(a==0)dfs(N-1,-1,a);
else dfs(0,-1,a);
}
bool B[MAXN];
typedef pair<pi,pi> pp;
vector<pp> sweep[MAXN]; // V[preA] = {index, postA, preB, postB}
struct node{
int s,e,m,v;
node *l,*r;
node(int _s,int _e):s(_s),e(_e){
m=(s+e)/2;
v=1e9;
if(s!=e){
l=new node(s,m);r=new node(m+1,e);
}
}
void up(int x,int va){
if(s==e){v=va;return;}
if(x<=m)l->up(x,va);
else r->up(x,va);
v=min(l->v,r->v);
}
int rmin(int x,int y){
if(s==x&&e==y)return v;
if(y<=m)return l->rmin(x,y);
else if (x>m)return r->rmin(x,y);
return min(l->rmin(x,m),r->rmin(m+1,y));
}
}*root;
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;
memset(p,-1,sizeof(p));
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);
// for(int i=0;i<N;++i)cout<<pre[1][i]<<' '<<post[1][i]<<'\n';
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];
for(int i=MAXL-1;i>=0;--i){
if(p[st][i][1] >= L[t]){
st=p[st][i][1];
}
}
int en=E[t];
for(int i=MAXL-1;i>=0;--i){
if(p[en][i][0] != -1 && p[en][i][0] <= R[t]){
en=p[en][i][0];
}
}
sweep[pre[1][st]].pb(mp(post[1][st], t), mp(pre[0][en], post[0][en]));
}
// In the seg tree pairs are (preB, preA)
root=new node(0,N-1);
for(int i=N-1;i>=0;--i){
int node = ipre[1][i];
root->up(pre[0][node], pre[1][node]);
for(auto x:sweep[i]){
int ind=x.f.s;
int m=root->rmin(x.s.f,x.s.s);
if(x.f.f >= m)A[ind]=1;
// cerr<<"Query "<<ind<<' '<<x.f.f<<' '<<m<<'\n';
}
}
return A;
}
