#include<bits/stdc++.h>
#include"werewolf.h"
using namespace std;
struct DSU{
vector<int>fa;
void init(int n){
fa.resize(n);
iota(fa.begin(),fa.end(),0);
}
int root(int u){return u==fa[u]?u:fa[u]=root(fa[u]);}
bool merge(int u,int v){
u=root(u),v=root(v);
if(u==v)return false;
fa[v]=u;
return true;
}
};
struct SegTree{
int n;
vector<int>t;
void init(int n){
this->n=n;
t.clear();
t.resize(2*n+2,0);
}
void add(int i,int v){
for(t[i+=n]+=v;i>>=1;)t[i]=t[i<<1]+t[i<<1|1];
}
int query(int l,int r){
int ret=0;
for(l+=n,r+=n+1;l<r;l>>=1,r>>=1){
if(l&1)ret+=t[l++];
if(r&1)ret+=t[--r];
}
return ret;
}
};
vector<vector<int>>fake1,fake2;
vector<int>tin1,tout1,ord1;
int t1=0;
void dfs1(int u){
tin1[u]=++t1;
ord1.push_back(u);
for(auto a:fake1[u]){
dfs1(a);
}
tout1[u]=t1;
}
vector<int>tin2,tout2,ord2;
int t2=0;
void dfs2(int u){
tin2[u]=++t2;
ord2.push_back(u);
for(auto a:fake2[u]){
dfs2(a);
}
tout2[u]=t2;
}
vector<int>check_validity(int n,vector<int>eu,vector<int>ev,vector<int>qs,vector<int>qe,vector<int>ql,vector<int>qr){
int q=qs.size();
vector<vector<int>>adj(n);
for(int a=0;a<eu.size();++a){
adj[eu[a]].push_back(ev[a]);
adj[ev[a]].push_back(eu[a]);
}
fake1=fake2=vector<vector<int>>(n);
DSU con;
vector<int>qq(q);iota(qq.begin(),qq.end(),0);
con.init(n);
sort(qq.begin(),qq.end(),[&](int i,int j)->bool{
return qr[i]<qr[j];
});
vector<int>qu(q),qv(q);
for(int a=0,qa=0;a<n;++a){
for(auto b:adj[a]){
if(b>=a)continue;
int ra=con.root(a),rb=con.root(b);
if(ra!=rb){
con.merge(ra,rb);
fake1[ra].push_back(rb);
}
}
while(qa<q&&qr[qq[qa]]<=a){
qv[qq[qa]]=con.root(qe[qq[qa]]);
++qa;
}
}
con.init(n);
sort(qq.begin(),qq.end(),[&](int i,int j)->bool{
return ql[i]>ql[j];
});
for(int a=n-1,qa=0;a>=0;--a){
for(auto b:adj[a]){
if(b<=a)continue;
int ra=con.root(a),rb=con.root(b);
if(ra!=rb){
con.merge(ra,rb);
fake2[ra].push_back(rb);
}
}
while(qa<q&&ql[qq[qa]]>=a){
qu[qq[qa]]=con.root(qs[qq[qa]]);
++qa;
}
}
tin1.resize(n);tout1.resize(n);
tin2.resize(n);tout2.resize(n);
ord1.clear();
ord2.clear();
t1=t2=-1;
dfs1(n-1);
dfs2(0);
vector<int>point(n);
vector<vector<pair<int,bool>>>event(n+1);
for(int a=0;a<n;++a)point[a]=tin2[ord1[a]];
for(int a=0;a<q;++a){
event[tin1[qv[a]]].push_back({a,true});
event[tout1[qv[a]]+1].push_back({a,false});
}
SegTree pro;
pro.init(n);
vector<int>ans(q,0);
for(int a=0;a<=n;++a){
for(auto b:event[a]){
if(b.second)ans[b.first]-=pro.query(tin2[qu[b.first]],tout2[qu[b.first]]);
else ans[b.first]+=pro.query(tin2[qu[b.first]],tout2[qu[b.first]]);
}
if(a<n)pro.add(point[a],1);
}
for(auto&a:ans)a=(a>0);
return ans;
}
