#include "werewolf.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
vector<int> x,y,s,e,l,r,a;
int n,q,m;
int newnode; // for creating nodes. starts at n.
vector<int> p(200005, -1); // for dsu
vector<pair<int,int>> ch(600005, {-1, -1}); // for preorder dfs.
vector<pair<int,int>> range(600005, {1e9, -1}); // node index --> top tree ord range.
vector<int> hr(200005, -1), wr(200005, -1);
vector<int> val(600005, -1); // store weight of node.
vector<int> ord(200005, -1); // order in top tree.
vector<int> botord(200005, -1); // bottom order stored in segment tree.
int mxn=200005, fw[200005];
void upd(int x, int v){
if(x <= 0)return;
while(x <= mxn){
fw[x]+=v;
x+=(x&(-x));
}
}
int qry(int x){
int res=0;
while(x > 0){
res+=fw[x];
x-=(x&(-x));
}
return res;
}
int par(int x){
if(p[x]==-1)return x;
else return p[x]=par(p[x]);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
swap(n,N);swap(x,X);swap(y,Y);swap(s,S);swap(E,e);swap(l,L);swap(R,r);
q=s.size(), m=x.size(), newnode=n;
vector<pair<int,int>> ed;
for(int i=0;i<m;i++){
ed.push_back({x[i], y[i]});
}
sort(ed.begin(),ed.end(), [&](auto a, auto b){
return min(a.f,a.s) > min(b.f,b.s);
});
vector<int> qs; for(int i=0;i<q;i++)qs.push_back(i);
int ptr;
sort(qs.begin(),qs.end(),[&](auto a, auto b){
return l[a] > l[b];
});
ptr=0;
int topnode;
for(auto [a, b] : ed){
int pa=par(a), pb=par(b);
//~ cout<<pa<<" "<<pb<<endl;
if(pa!=pb){
int v=min(a, b);
while(ptr < q and l[qs[ptr]] > v){
hr[qs[ptr]]=par(s[qs[ptr]]);
ptr++;
}
//~ printf("top from %d to %d, par %d to %d, index %d\n", a, b, pa, pb, newnode);
//~ fflush(stdout);
val[newnode]=v;
topnode=newnode;
ch[newnode].f=pa,ch[newnode].s=pb;
p[pa]=newnode;
p[pb]=newnode;
newnode++;
}
}
while(ptr < q){
hr[qs[ptr]]=par(s[qs[ptr]]);
ptr++;
}
int nodesreached;
nodesreached=1;
auto dfs=[&](auto dfs, int x) -> void {
if(ch[x].f==-1){
ord[x]=nodesreached;
range[x].f=nodesreached, range[x].s=nodesreached;
nodesreached++;
}
else {
dfs(dfs,ch[x].f);
dfs(dfs,ch[x].s);
//~ assert(range[ch[x].f].s==range[ch[x].s].f-1);
range[x].f=min(range[ch[x].f].f, range[ch[x].s].f);
range[x].s=max(range[ch[x].s].s, range[ch[x].f].s);
}
//~ printf("dfs at %d, range is %d,%d, ch %d,%d\n", x, range[x].f,range[x].s, ch[x].f, ch[x].s);
};
dfs(dfs, topnode);
// now do the bottom tree.
// reset a bunch of stuff
for(int i=0;i<n;i++)p[i]=-1;
sort(ed.begin(),ed.end(), [&](auto a, auto b){
return max(a.f,a.s) < max(b.f,b.s);
});
sort(qs.begin(),qs.end(),[&](auto a, auto b){
return r[a] < r[b];
});
ptr=0;
int bottomnode;
for(auto [a, b] : ed){
int pa=par(a), pb=par(b);
if(pa!=pb){
int v=max(a, b);
while(ptr < q and r[qs[ptr]] < v){
wr[qs[ptr]]=par(e[qs[ptr]]);
ptr++;
}
val[newnode]=v;
ch[newnode].f=pa,ch[newnode].s=pb;
bottomnode=newnode;
p[pa]=newnode;
p[pb]=newnode;
//~ printf("bot from %d to %d, par %d to %d, index %d\n", a, b, pa, pb, newnode);
//~ fflush(stdout);
newnode++;
}
}
while(ptr < q){
wr[qs[ptr]]=par(e[qs[ptr]]);
ptr++;
}
nodesreached=1;
auto dfs2=[&](auto dfs2, int x) -> void {
if(ch[x].f==-1){
botord[ord[x]]=nodesreached;
range[x].f=nodesreached;
range[x].s=nodesreached;
//~ printf("dfs2 leaf, ind %d, ord %d, botord %d\n",x,ord[x],nodesreached);
nodesreached++;
}
else {
dfs2(dfs2,ch[x].f);
dfs2(dfs2,ch[x].s);
range[x].f=min(range[ch[x].f].f, range[ch[x].s].f);
range[x].s=max(range[ch[x].s].s, range[ch[x].f].s);
}
};
dfs2(dfs2, bottomnode);
for(int i=1;i<=n;i++){
assert(botord[i]!=-1);
//~ botordtoind[botord[ord[i]]]=i; // this should be a permutation.
//~ cout<<botordtoind[i]<<" ";
}
vector<int> ans(q, 0);
vector<vector<pair<int,int>>> todo(n+1);
for(int i=0;i<q;i++){
//~ range[hr[i]].s++; // one index.
//~ range[wr[i]].s++;
todo[range[hr[i]].f-1].push_back({i, 0}); // (l, r]
todo[range[hr[i]].s].push_back({i, 1});
//~ printf("%d %d , %d %d\n",
//~ range[hr[i]].f, range[hr[i]].s, range[wr[i]].f, range[wr[i]].s);
}
for(int i=1;i<=n;i++){
upd(ord[i], 1);
//~ cout<<endl<<i<<endl;
for(auto [qind, type] : todo[i]){
//~ cout<<qind<<" " <<type<<endl;
int up, down;
up=qry(range[wr[qind]].s);
down=qry(range[wr[qind]].f-1);
if(type==0)ans[qind]-=up-down;
else ans[qind]+=up-down;
//~ printf("qind %d, type %d, s %d, f %d, up %d down %d\n",
//~ qind, type, range[wr[qind]].s, range[wr[qind]].f-1, up, down);
}
}
vector<int> A(q);
//~ for(auto it : st){
//~ cout<<it.f << " " <<it.s<<endl;
//~ }
for (int i = 0; i < q; ++i) {
if(ans[i] > 0)A[i]=1;
else A[i]=0;
}
return A;
}
/*
6 6 3
0 3
3 1
3 4
1 2
2 5
1 5
4 2 1 2
4 2 2 2
5 4 3 4
*/
//~ 1 6 , 2 4
//~ 1 3 , 2 5
//~ 5 6 , 0 5
