#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MX=5e5;
class RootedTree {
public:
RootedTree() {
RE(i,MX) p[i] = -1;
}
void addChild(int parent, int child) {
chl[parent].pb(child);
p[child] = parent;
}
void createA(int u) {
a[m] = u;
bg[u] = m++;
for(int v:chl[u]) createA(v);
ed[u] = m-1;
}
void createA() {
createA(root);
}
vi chl[MX];
int p[MX];
int root;
int a[MX], bg[MX], ed[MX];
int m=0;
};
int m, q, n;
vi adj[MX];
vi atL[MX], atR[MX];
vi A, X, Y, S, E, L, R;
int p[MX], r[MX];
RootedTree treeH, treeW;
int SEG[MX*4];
int SA[MX];
int getSet(int i) {return i==p[i]?i:p[i]=getSet(p[i]);}
bool isSameSet(int i, int j) {return getSet(i)==getSet(j);}
void unionSet(int i, int j) {
if(!isSameSet(i,j)) {
i=getSet(i), j=getSet(j);
p[j] = i;
}
}
void setSeg(int i, int x, int p=0, int l=0, int r=n-1) {
if(i < l || i > r) return;
if(l == r) {
SEG[p] = x;
return;
}
int m=(l+r)/2;
setSeg(i,x,p*2+1,l,m);
setSeg(i,x,p*2+2,m+1,r);
SEG[p] = max(SEG[p*2+1], SEG[p*2+2]);
}
int getSeg(int i, int j, int p=0, int l=0, int r=n-1) {
if(j < l || i > r) return -1;
if(i <= l && j >= r) return SEG[p];
int m=(l+r)/2;
int a=getSeg(i,j,p*2+1,l,m);
int b=getSeg(i,j,p*2+2,m+1,r);
return max(a,b);
}
vi check_validity(int N, vi _X, vi _Y, vi _S, vi _E, vi _L, vi _R) {
n = N;
m = _X.size();
q = _S.size();
L=_L, R=_R, X=_X, Y=_Y, S=_S, E=_E;
A.assign(q, 0);
RE(i,m) {
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
RE(i,q) {
atL[L[i]].pb(i);
atR[R[i]].pb(i);
}
RE(i,n) p[i]=i, r[i]=0;
RE(i,n) {
for(int j:adj[i]) {
if(j > i || isSameSet(i,j)) continue;
j = getSet(j);
unionSet(i,j);
treeW.addChild(i,j);
}
for(int j:atR[i]) E[j] = getSet(E[j]);
}
treeW.root = n-1;
RE(i,n) p[i]=i, r[i]=0;
REV(i,0,n) {
for(int j:adj[i]) {
if(j < i ||isSameSet(i,j)) continue;
j = getSet(j);
unionSet(i,j);
treeH.addChild(i,j);
}
for(int j:atL[i]) S[j] = getSet(S[j]);
}
treeH.root = 0;
treeW.createA();
treeH.createA();
viii queries;
RE(curQ,q) {
int bg, ed;
int u = S[curQ];
bg = treeH.bg[u];
ed = treeH.ed[u];
queries.pb(tie(ed,bg,curQ));
}
sort(queries.begin(), queries.end());
RE(i,n*4) SEG[i] = -1;
RE(i,n) SA[treeW.a[i]] = i;
int j=0;
for(iii p : queries) {
int bg, ed, curQ;
tie(ed, bg, curQ) = p;
while(j <= ed) {
setSeg(SA[treeH.a[j]],j);
j++;
}
int u = E[curQ];
if(getSeg(treeW.bg[u], treeW.ed[u]) >= bg) {
A[curQ] = 1;
} else {
A[curQ] = 0;
}
}
return A;
}
