#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> con[200005],con_arb[200005];
int tin[200005][2],tout[200005][2],timer,who[200005][2];
int anc[200005][18][2];
int parent[200005][2];
int father[200005],siz[200005],sus[200005];
void init()
{
for(int i=0;i<n;i++)
father[i]=i, siz[i]=1, sus[i]=i;
}
int gas(int x)
{
if(father[x]!=x)
father[x] = gas(father[x]);
return father[x];
}
void unite(int x, int y, int c)//x are prioritate
{
x = gas(x);
y = gas(y);
if(x==y)
return;
if(siz[x] >= siz[y])
{
father[y] = x;
parent[sus[y]][c] = sus[x];
siz[x] += siz[y];
}
else
{
parent[sus[y]][c] = sus[x];
sus[y] = sus[x];
father[x] = y;
siz[y] += siz[x];
}
}
void dfs(int nod, int c)
{
timer++;
who[timer][c] = nod;
tin[nod][c] = timer;
for(int adj:con_arb[nod])
{
dfs(adj,c);
}
tout[nod][c] = timer;
}
void calc_arb(int c)
{
for(int i=0;i<n;i++)
{
parent[i][c] = -1;
con_arb[i].clear();
}
vector<int> ord;
if(c==0)
{
for(int i=0;i<n;i++)
ord.push_back(i);
}
else
{
for(int i=n-1;i>=0;i--)
ord.push_back(i);
}
init();
vector<bool> apare(n,0);
for(int i:ord)
{
apare[i] = 1;
for(int x:con[i])
{
if(apare[x])
{
unite(i,x,c);
}
}
}
//for(int i=0;i<n;i++) cerr<<i<<" "<<parent[i][c]<<" "<<c<<" parent\n";
for(int i=0;i<n;i++)
{
if(parent[i][c]==-1)
{
anc[i][0][c] = i;
}
else
{
anc[i][0][c] = parent[i][c];
con_arb[parent[i][c]].push_back(i);
}
}
for(int p=1;p<18;p++)
for(int i=0;i<n;i++)
anc[i][p][c] = anc[anc[i][p-1][c]][p-1][c];
timer=0;
dfs(ord.back(),c);
}
int get_anc(int nod, int c, int lim)
{
if(c==1)
{
for(int p=17;p>=0;p--)
if(anc[nod][p][c] >= lim)
nod = anc[nod][p][c];
return nod;
}
else
{
for(int p=17;p>=0;p--)
if(anc[nod][p][c] <= lim)
nod = anc[nod][p][c];
return nod;
}
}
int aib[200005];
int qry(int poz)
{
int aux=0;
for(int i=poz;i>0;i-=(i&(-i)))
aux += aib[i];
return aux;
}
void upd(int poz, int newv)
{
for(int i=poz;i<=n;i+=(i&(-i)))
aib[i] += newv;
}
vector<pair<pair<int,int>,pair<int,int>>> qrys;
vector<pair<int,pair<int,int>>> queries[200005];
int sol[200005];
void solve_qrys()
{
for(auto [x,id]:qrys)
{
/*int cnt=0;
for(int i=0;i<n;i++)
if(tin[i][0]<=x.first && tin[i][1]<=x.second)
cnt++;
sol[id.first] += cnt*id.second;*/
queries[x.first].push_back({x.second,id});
}
for(int i=1;i<=n;i++)
{
upd(tin[who[i][0]][1], +1);
for(auto [x,id]:queries[i])
{
sol[id.first] += qry(x)*id.second;
}
}
}
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<X.size();i++)
{
con[X[i]].push_back(Y[i]);
con[Y[i]].push_back(X[i]);
}
calc_arb(0);
calc_arb(1);
for(int i=0;i<L.size();i++)
{
int v1 = get_anc(S[i],1,L[i]);
int v0 = get_anc(E[i],0,R[i]);
qrys.push_back({{tout[v0][0],tout[v1][1]},{i,+1}});
qrys.push_back({{tout[v0][0],tin[v1][1]-1},{i,-1}});
qrys.push_back({{tin[v0][0]-1,tout[v1][1]},{i,-1}});
qrys.push_back({{tin[v0][0]-1,tin[v1][1]-1},{i,+1}});
}
solve_qrys();
vector<int> afis(L.size(),0);
for(int i=0;i<L.size();i++)
afis[i] = (sol[i]!=0);
return afis;
}
