#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
const int MAXQ = 2e5;
int N, M, Q;
vector<int> S, E, L, R, ans;
struct UF
{
int par[MAXN+10];
void init() { for(int i=0; i<N; i++) par[i]=i; }
int Find(int x) { return (x==par[x])?x:(par[x]=Find(par[x])); }
}uf1, uf2;
vector<int> adj[MAXN+10], adj1[MAXN+10], adj2[MAXN+10];
int s1[MAXN+10], e1[MAXN+10], s2[MAXN+10], e2[MAXN+10], cnt;
int par1[MAXN+10][25], par2[MAXN+10][25];
void dfs(int now, int *s, int *e, vector<int> *adj)
{
s[now]=cnt++; e[now]=s[now];
for(int nxt : adj[now])
{
dfs(nxt, s, e, adj);
e[now]=max(e[now], e[nxt]);
}
}
int A[MAXN+10];
vector<int> tree[4*MAXN+10];
void init(int node, int tl, int tr)
{
if(tl==tr)
{
tree[node].push_back(A[tl]);
return;
}
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
tree[node].resize(tree[node*2].size()+tree[node*2+1].size());
merge(tree[node*2].begin(), tree[node*2].end(), tree[node*2+1].begin(), tree[node*2+1].end(), tree[node].begin());
}
int query(int node, int tl, int tr, int xl, int xr, int yl, int yr)
{
if(tr<xl || xr<tl) return 0;
if(xl<=tl && tr<=xr) return upper_bound(tree[node].begin(), tree[node].end(), yr)-lower_bound(tree[node].begin(), tree[node].end(), yl);
int mid=tl+tr>>1;
return query(node*2, tl, mid, xl, xr, yl, yr)+query(node*2+1, mid+1, tr, xl, xr, yl, yr);
}
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 i, j;
N=_N; S=_S; E=_E; L=_L; R=_R; M=X.size(), Q=S.size(); ans.resize(Q);
for(i=0; i<M; i++)
{
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
uf1.init(); par1[0][0]=0;
for(i=N-1; i>=0; i--)
{
int now=i;
for(int nxt : adj[now])
{
if(nxt<now) continue;
nxt=uf1.Find(nxt);
if(now==nxt) continue;
uf1.par[nxt]=now; par1[nxt][0]=now;
adj1[now].push_back(nxt);
}
}
uf2.init(); par2[N-1][0]=N-1;
for(i=0; i<N; i++)
{
int now=i;
for(int nxt : adj[now])
{
if(nxt>now) continue;
nxt=uf2.Find(nxt);
if(now==nxt) continue;
uf2.par[nxt]=now; par2[nxt][0]=now;
adj2[now].push_back(nxt);
}
}
cnt=0; dfs(0, s1, e1, adj1);
cnt=0; dfs(N-1, s2, e2, adj2);
for(i=0; i<N; i++) A[s1[i]]=s2[i];
init(1, 0, N-1);
for(j=1; j<=20; j++) for(i=0; i<N; i++) par1[i][j]=par1[par1[i][j-1]][j-1];
for(j=1; j<=20; j++) for(i=0; i<N; i++) par2[i][j]=par2[par2[i][j-1]][j-1];
for(i=0; i<Q; i++)
{
int s=S[i], e=E[i];
if(S[i]<L[i] || E[i]>R[i]) continue;
for(j=20; j>=0; j--) if(par1[s][j]>=L[i]) s=par1[s][j];
for(j=20; j>=0; j--) if(par2[e][j]<=R[i]) e=par2[e][j];
if(query(1, 0, N-1, s1[s], e1[s], s2[e], e2[e])) ans[i]=1;
}
return ans;
}
