#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
int a,b;
pair<int,int> edge[1000005];
vector<int> z[1000005][2];
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);
}
int val[1000005][2];
int up[400005][20][2];
int root1,root2,tour1,tour2;
int rev[1000005][2];
struct dsu{
int par[1000005];
int root;
void init(){
for (int i=1;i<=a;i++){
par[i]=i;
}
}
int find(int u){
if (par[u]==u){
return u;
}
return par[u]=find(par[u]);
}
void join(int x,int y,int t){
x=find(x);
y=find(y);
if (x==y){
return;
}
z[x][t].push_back(y);
root=x;
par[y]=x;
}
};
dsu d;
int par[200005][21][2];
int sta[1000005][2];
int fin[1000005][2];
int tour;
void dfs(int i,int t){
tour++;
sta[i][t]=tour;
rev[tour][t]=i;
for (auto p:z[i][t]){
par[p][0][t]=i;
dfs(p,t);
}
fin[i][t]=tour;
}
struct node{
int l,r,base,id;
};
vector<node> pos[1000005];
int res[100005];
int bit[4000005];
void update(int i,int val){
i++;
while (i<=a+64){
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();
vector <int> ans(q);
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]++;
}
for (int i=0;i<b;i++){
edge[i]={X[i],Y[i]};
}
sort(edge,edge+b,cmp);
d.init();
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);
}
root1=d.root;
sort(edge,edge+b,cmp1);
d.init();
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);
}
root2=d.root;
dfs(root2,1);
tour=0;
dfs(root1,0);
for (int j=1;j<=20;j++){
for (int i=1;i<=a;i++){
par[i][j][0]=par[par[i][j-1][0]][j-1][0];
par[i][j][1]=par[par[i][j-1][1]][j-1][1];
}
}
for (int i=0;i<q;i++){
int x=S[i];
int y=E[i];
int l=L[i];
int r=R[i];
for (int j=20;j>=0;j--){
if (par[x][j][1]>=l){
x=par[x][j][1];
}
if (par[y][j][0]<=r && par[y][j][0]!=0){
y=par[y][j][0];
}
}
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=0;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));
}
}
for (int i=0;i<q;i++){
ans[i]=(res[i]>0);
}
return ans;
}
