#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
int a;
struct dsu{
vector<int> par;
int root;
void init(int n){
par.assign(n+1,0);
for (int i=1;i<=n;i++) par[i]=i;
root=1;
}
int find(int u){
if (par[u]==u) return u;
return par[u]=find(par[u]);
}
void join(int x,int y,int t,vector<vector<int>>& z){
x=find(x); y=find(y);
if (x==y) return;
z[x].push_back(y);
root=x;
par[y]=x;
}
} d;
struct node{
int l,r,base,id;
};
int root1,root2,tour;
vector<array<int,2>> rev,sta,fin;
vector<array<int,21>> par0,par1;
vector<vector<int>> z0,z1;
vector<vector<node>> pos;
vector<int> res;
vector<int> bit;
bool cmp(pair<int,int> a,pair<int,int> b){
return max(a.first,a.second)<max(b.first,b.second);
}
bool cmp1(pair<int,int> a,pair<int,int> b){
return min(a.first,a.second)>min(b.first,b.second);
}
void dfs(int i,int t,vector<vector<int>>& z,vector<array<int,2>>& sta,vector<array<int,2>>& fin,vector<array<int,2>>& rev,vector<array<int,21>>& par){
tour++;
sta[i][t]=tour;
rev[tour][t]=i;
for (auto p:z[i]){
if (t==0) par[p][0]=par[i][0];
else par[p][0]=par[i][0];
dfs(p,t,z,sta,fin,rev,par);
}
fin[i][t]=tour;
}
void update(int i,int val){
i++;
while (i<(int)bit.size()){
bit[i]+=val;
i+=i&-i;
}
}
int query(int i){
i++;
int res=0;
while (i>0){
res+=bit[i];
i-=i&-i;
}
return res;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
int q=L.size();
a=N;
int b=X.size();
for (int i=0;i<b;i++){ X[i]++; Y[i]++; }
for (int i=0;i<q;i++){ L[i]++; R[i]++; S[i]++; E[i]++; }
vector<pair<int,int>> edge(b);
for (int i=0;i<b;i++) edge[i]={X[i],Y[i]};
z0.assign(a+5,{}); z1.assign(a+5,{});
rev.assign(a+5,{0,0});
sta.assign(a+5,{0,0});
fin.assign(a+5,{0,0});
par0.assign(a+5,{0}); par1.assign(a+5,{0});
pos.assign(a+5,{});
res.assign(q,0);
bit.assign(a+200,0);
sort(edge.begin(),edge.end(),cmp);
d.init(a);
for (int i=0;i<b;i++){
int u=max(edge[i].first,edge[i].second);
int v=min(edge[i].first,edge[i].second);
d.join(u,v,0,z0);
}
root1=d.root;
sort(edge.begin(),edge.end(),cmp1);
d.init(a);
for (int i=0;i<b;i++){
int u=min(edge[i].first,edge[i].second);
int v=max(edge[i].first,edge[i].second);
d.join(u,v,1,z1);
}
root2=d.root;
tour=0;
dfs(root2,1,z1,sta,fin,rev,par1);
tour=0;
dfs(root1,0,z0,sta,fin,rev,par0);
for (int j=1;j<=20;j++){
for (int i=1;i<=a;i++){
if (par0[i][j-1]) par0[i][j]=par0[par0[i][j-1]][j-1];
if (par1[i][j-1]) par1[i][j]=par1[par1[i][j-1]][j-1];
}
}
for (int i=0;i<q;i++){
int x=S[i],y=E[i],l=L[i],r=R[i];
for (int j=20;j>=0;j--){
if (par1[x][j]>=l) x=par1[x][j];
if (par0[y][j]<=r && par0[y][j]!=0) y=par0[y][j];
}
pos[sta[x][1]-1].push_back({sta[y][0],fin[y][0],-1,i});
pos[fin[x][1]].push_back({sta[y][0],fin[y][0],1,i});
}
for (int i=1;i<=a;i++){
update(sta[rev[i][1]][0],1);
for (auto p:pos[i]){
res[p.id]+=p.base*(query(p.r)-query(p.l-1));
}
}
vector<int> ans(q);
for (int i=0;i<q;i++) ans[i]=(res[i]>0);
return ans;
}
