#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#include "werewolf.h"
using namespace std;
ll N;
vector<ll> c[200005], g1[200005], g2[200005];
ll in1[200005], out1[200005], in2[200005], out2[200005];
ll bn1[200005][20], bn2[200005][20];
vector<ll> v1, v2;
void dfs1(int h,int p)
{
bn1[h][0]=p;
for (int i = 1; i < 20; i++)
if (bn1[h][i-1]!=N) bn1[h][i]=bn1[bn1[h][i-1]][i-1]; else bn1[h][i]=N;
in1[h]=v1.size();
v1.pb(h);
for (int i = 0; i < g1[h].size(); i++)
dfs1(g1[h][i], h);
out1[h]=v1.size();
v1.pb(h);
}
void dfs2(int h,int p=-1)
{
bn2[h][0]=p;
for (int i = 1; i < 20; i++)
if (bn2[h][i-1]!=-1)bn2[h][i]=bn2[bn2[h][i-1]][i-1]; else bn2[h][i]=-1;
in2[h]=v2.size();
v2.pb(h);
for (int i = 0; i < g2[h].size(); i++)
dfs2(g2[h][i], h);
out2[h]=v2.size();
v2.pb(h);
}
ll d[1600001];
void build(int h,int l,int r)
{
if (l==r)
{
d[h]=-1;
return;
}
int w=(l+r)/2;
build(h*2,l,w);
build(h*2+1,w+1,r);
d[h]=max(d[h*2], d[h*2+1]);
}
ll get(int h,int l,int r,int x,int y)
{
if (x>y) return -1;
if (l==x && y==r) return d[h];
int w=(l+r)/2;
return max(get(h*2,l,w,x,min(y,w)), get(h*2+1,w+1,r,max(x,w+1),y));
}
void update(int h,int l,int r,int x,int k)
{
if (l==r)
{
d[h]=k;
return;
}
int w=(l+r)/2;
if (x<=w) update(h*2,l,w,x,k); else update(h*2+1,w+1,r,x,k);
d[h]=max(d[h*2], d[h*2+1]);
}
struct dsu
{
ll d[1000001];
void make_sets(int h)
{
for (int i = 0; i <= h; i++)
d[i]=i;
}
ll find_set(int h)
{
if (h==d[h]) return h; else return d[h]=find_set(d[h]);
}
bool unite_sets(int x,int y)
{
x=find_set(x);
y=find_set(y);
if (x!=y)
{
d[y]=x;
return 1;
}
return 0;
}
} gg;
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 < x.size(); i++)
{
c[x[i]].pb(y[i]);
c[y[i]].pb(x[i]);
}
N=n;
vector<int> ans;
ans.resize(s.size());
gg.make_sets(n);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < c[i].size(); j++)
if (c[i][j]<i)
{
ll to=gg.find_set(c[i][j]);
if (gg.unite_sets(i, to))
{
g1[i].pb(to);
//cout << " " << i << " " << to << "\n";
}
}
}
gg.make_sets(n);
for (int i = n-1; i > -1; i--)
{
for (int j = 0; j < c[i].size(); j++)
if (c[i][j]>i)
{
ll to=gg.find_set(c[i][j]);
if (gg.unite_sets(i, to))
{
g2[i].pb(to);
//cout << i << " " << to << "\n";
}
}
}
dfs1(n-1, n);
dfs2(0, -1);
ll m=s.size();
vector<pair<pair<pll, pll>, ll> > zp;
for (int i = 0; i < m; i++)
{
ll x, y;
x=s[i];
for (int j = 19; j > -1; j--)
if (bn2[x][j]>=l[i]) x=bn2[x][j];
y=e[i];
for (int j = 19; j > -1; j--)
if (bn1[y][j]<=r[i]) y=bn1[y][j];
//cout << x << " " << y << " " << e[i] << "\n";
zp.pb(mp(mp(mp(out2[x], in2[x]), mp(in1[y], out1[y])), i));
}
sort(all(zp));
ll lr=-1;
for (int i = 0; i < v2.size(); i++)
{
update(1,0,v1.size()-1,in1[v2[i]], i);
update(1,0,v1.size()-1,out1[v2[i]], i);
while (lr+1<zp.size() && i==zp[lr+1].fi.fi.fi)
{
lr++;
if (get(1, 0, v1.size()-1, zp[lr].fi.se.fi, zp[lr].fi.se.se)>=zp[lr].fi.fi.se) ans[zp[lr].se]=1;
}
}
return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
