#include "werewolf.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fir first
#define sec second
using namespace std;
typedef struct qry{
int s, e, l, r, idx;
}qry;
const int mxN=200200;
int N, M, Q;
qry A[mxN];
vector <pii> E;
vector <int> adj[mxN], adjr[mxN], adjl[mxN];
int inl[mxN], outl[mxN], inr[mxN], outr[mxN], invr[mxN];
int eidx;
vector <pii> cont[mxN];
vector <int> ans;
int par[mxN];
void init_uf(){for(int i=0;i<N;i++) par[i]=i;}
int findpar(int a){return (par[a]==a ? a : par[a]=findpar(par[a]));}
void onion(int a, int b, bool inv)
{
int p=findpar(a), q=findpar(b);
if(inv) par[max(p, q)]=min(p, q);
else par[min(p, q)]=max(p, q);
}
void dfsr(int now)
{
inr[now]=eidx;
for(int nxt : adjr[now]) dfsr(nxt);
outr[now]=eidx++;
invr[outr[now]]=now;
}
void dfsl(int now)
{
inl[now]=eidx;
for(int nxt : adjl[now]) dfsl(nxt);
outl[now]=eidx++;
}
int seg[4*mxN];
void upd(int idx, int s, int e, int pos)
{
if(s==e)
{
seg[idx]++;
return;
}
int mid=(s+e)/2;
if(pos<=mid) upd(2*idx, s, mid, pos);
else upd(2*idx+1, mid+1, e, pos);
seg[idx]++;
}
int solv(int idx, int s1, int e1, int s2, int e2)
{
if(s1>e2 || s2>e1) return 0;
if(s2<=s1 && e1<=e2) return seg[idx];
int mid=(s1+e1)/2;
return solv(2*idx, s1, mid, s2, e2)+solv(2*idx+1, mid+1, e1, s2, e2);
}
std::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) {
N=n;
M=X.size();
Q = S.size();
ans.resize(Q);
for(int i=0;i<Q;i++)
{
A[i].s=S[i], A[i].e=E[i], A[i].l=L[i], A[i].r=R[i], A[i].idx=i;
}
for(int i=0;i<M;i++) adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);
init_uf();
sort(A, A+Q, [](qry a, qry b){return a.r<b.r;});
int cur=0;
for(int i=0;i<Q;i++)
{
while(cur<A[i].r)
{
for(int ele : adj[cur+1]) if(ele<=cur) onion(ele, cur+1, false);
cur++;
}
if(A[i].e>A[i].r) A[i].e=-1;
else A[i].e=findpar(A[i].e);
}
init_uf();
sort(A, A+Q, [](qry a, qry b){return a.l>b.l;});
cur=N-1;
for(int i=0;i<Q;i++)
{
while(cur>A[i].l)
{
for(int ele : adj[cur-1]) if(ele>=cur) onion(ele, cur-1, true);
cur--;
}
if(A[i].s<A[i].l) A[i].s=-1;
else A[i].s=findpar(A[i].s);
}
sort(A, A+Q, [](qry a, qry b){return a.idx<b.idx;});
init_uf();
for(int i=1;i<N;i++) for(int ele : adj[i]) if(ele<i && findpar(ele)!=i)
{
adjr[i].push_back(findpar(ele));
onion(ele, i, false);
}
init_uf();
for(int i=N-1;i>=0;i--) for(int ele : adj[i]) if(ele>i && findpar(ele)!=i)
{
adjl[i].push_back(findpar(ele));
onion(ele, i, true);
}
eidx=1;
dfsr(N-1);
eidx=1;
dfsl(0);
for(int i=0;i<Q;i++)
{
if(A[i].s==-1 || A[i].e==-1) continue;
cont[inr[A[i].e]-1].emplace_back(i, -1);
cont[outr[A[i].e]].emplace_back(i, 1);
}
for(int i=1;i<=N;i++)
{
int now=invr[i];
upd(1, 1, N, outl[now]);
for(pii ele : cont[i])
{
pii rng=pii(inl[A[ele.fir].s], outl[A[ele.fir].s]);
ans[ele.fir]+=solv(1, 1, N, rng.fir, rng.sec)*ele.sec;
}
}
for(int i=0;i<Q;i++)
{
if(A[i].s==-1 || A[i].e==-1) ans[i]=0;
else if(ans[i]!=0) ans[i]=1;
}
return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
