#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
#define left h*2,l,(l + r)/2
#define right h*2+1,(l+r)/2 + 1,r
using namespace std;
const int NN = 2e5 + 3;
vector <int> v[NN],g[4][NN],t[4*NN];
int p[NN],par[4][NN],d[5][25][NN],timer;
int tin[4][NN],tout[4][NN],rev[4][NN];
bool active[NN],fix[NN];
int P(int x){
if (x==p[x]) return x;
return p[x]=P(p[x]);
}
void dsu(int id,int x,int y){
if (P(x) == P(y)) return;
y = P(y);
par[id][y] = x;
g[id][x].pb(y);
// cout<<"Edge "<<y<<" -> "<<x<<endl;
p[y] = x;
}
void dfs(int id,int x,int par){
d[id][0][x] = par;
// cout<<"> "<<id<<" "<<x<<endl;
tin[id][x] = ++timer;
rev[id][timer] = x;
for (int to: g[id][x]){
if (to != par) dfs(id,to,x);
}
tout[id][x] = timer;
}
vector <int> merge(vector <int> x,vector <int> y){
for (int yy: y)
x.pb(yy);
sort(x.begin(),x.end());
return x;
}
void build(int h,int l,int r){
if (l == r){
t[h].pb( tin[2][rev[1][l]]);
return;
}
build(left);
build(right);
t[h] = merge(t[h*2],t[h*2+1]);
}
int get(int h,int l,int r,int L,int R,int le,int ri){
if (r < L || R < l) return 0;
if (L <= l && r <= R){
int l1=0,r1=t[h].size()-1,res=-1;
while (l1 <= r1){
int mid = (l1+r1)>>1;
if (t[h][mid] >= le){
res=t[h][mid];
r1=mid-1;
}else{
l1=mid+1;
}
}
return (res >= le && res <= ri);
}
if (get(left,L,R,le,ri)) return 1;
return get(right,L,R,le,ri);
}
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) {
int Q = S.size(),n = N;
vector<int> ans(Q);
for (int i=0;i<X.size();i++){
v[X[i]].pb(Y[i]);
v[Y[i]].pb(X[i]);
}
for (int i=0;i<n;i++)
p[i] = i,par[1][i] = par[2][i] = -1;
for (int i = 0; i < n; i++){
active[i] = 1;
for (int to: v[i]){
if (active[to]) dsu(1,i,to);
}
}
for (int i=0;i<n;i++)
p[i] = i,par[1][i] = par[2][i] = -1,active[i] = 0;
for (int i = n-1; i >= 0; i--){
active[i] = 1;
for (int to: v[i]){
if (active[to]) dsu(2,i,to);
}
}
int root1,root2;
for (int i=0;i<n;i++){
if (par[1][i] == -1) root1 = i;
if (par[2][i] == -1) root2 = i;
}
timer=0; dfs(1,root1,root1);
timer=0; dfs(2,root2,root2);
build(1,1,n);
for (int j = 1; j < 20; j++){
for (int i=0;i<n;i++){
d[1][j][i] = d[1][j - 1][d[1][j - 1][i]];
d[2][j][i] = d[2][j - 1][d[2][j - 1][i]];
}
}
for (int i = 0; i < Q; i++){
int A = S[i],B = E[i],l = L[i],r = R[i];
for (int j = 19; j >= 0; j--) {
if (d[1][j][B] <= r) B = d[1][j][B];
if (d[2][j][A] >= l) A = d[2][j][A];
}
if (A < l || B > r) continue;
int l1 = tin[1][B],r1 = tout[1][B];
int l2 = tin[2][A],r2 = tout[2][A];
ans[i] = get(1,1,n,l1,r1,l2,r2);
}
return ans;
}
