#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using pii = pair<int, int>;
const int N = 2e5 + 10;
vector<int> rad[2][N],adj[2][N],QL[N],QR[N],QU[2][N];
int st[2][N],fn[2][N],p[2][N],T[2],rv[2][N],f[N];
int gp(int c, int x){
return p[c][x]!=x?p[c][x]=gp(c,p[c][x]):x;
}
void uni(int c, int v, int u){
u=gp(c,u);
if(v==u) return;
adj[c][v].pb(u);
p[c][u]=v;
}
void dfs(int c, int v){
st[c][v]=++T[c];
rv[c][T[c]]=v;
for(int u : adj[c][v]) dfs(c,u);
fn[c][v]=T[c];
}
void upd(int t, int x){
for(; t<N; t+=t&-t) f[t]+=x;
}
int gt(int t, int x=0){
for(; t; t-=t&-t) x+=f[t];
return x;
}
int get(int l, int r){
return gt(r)-gt(l-1);
}
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 M=X.size(), Q=S.size();
for(int i=0; i<Q; i++){
QL[L[i]].pb(i);
QR[R[i]].pb(i);
}
vector<int> A(Q);
for(int i=0; i<M; i++){
if(X[i]>Y[i]) swap(X[i],Y[i]);
rad[0][Y[i]].pb(X[i]);
rad[1][X[i]].pb(Y[i]);
}
for(int i=0; i<N; i++) p[0][i]=p[1][i]=i;
for(int i=0; i<N; i++){
for(int j : rad[0][i]) uni(0,i,j);
for(int j : QR[i]){
E[j]=gp(0,E[j]);
}
}
for(int i=N; i--; ){
for(int j : rad[1][i]) uni(1,i,j);
for(int j : QL[i]){
S[j]=gp(1,S[j]);
}
}
dfs(0,N-1);
dfs(1,0);
for(int i=0; i<Q; i++){
QU[0][st[0][E[i]]-1].pb(i);
QU[1][fn[0][E[i]]].pb(i);
}
for(int i=1; i<=N; i++){
upd(st[1][rv[0][i]],1);
for(int j : QU[0][i]) A[j]-=get(st[1][S[j]],fn[1][S[j]]);
for(int j : QU[1][i]) A[j]+=get(st[1][S[j]],fn[1][S[j]]);
}
for(int i=0; i<Q; i++) if(A[i]) A[i]=1;
return A;
}
