#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 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)
{
}
else
{
con_arb[parent[i][c]].push_back(i);
}
}
timer=0;
dfs(ord.back(),c);
}
int get_anc(int nod, int c, int lim)
{
if(c==1)
{
while(parent[nod][c]!=-1 && parent[nod][c] >= lim)
nod = parent[nod][c];
return nod;
}
else
{
while(parent[nod][c]!=-1 && parent[nod][c] <= lim)
nod = parent[nod][c];
return nod;
}
}
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);
vector<int> sol(L.size(), 0);
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]);
for(int u=tin[v0][0];u<=tout[v0][0];u++)
{
int x = who[u][0];
if(tin[v1][1] <= tin[x][1] && tin[x][1] <= tout[v1][1])
{
sol[i] = 1;
break;
}
}
}
return sol;
}
