#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7, LG=20;
vi V[LIM], pytania[LIM], dodaj[LIM];
vector<pair<int,int>>kraw;
set<int>zbior[LIM];
int Fl[LIM], pocz[LIM], kon[LIM], nxt[LIM][LG], lpre;
int Fr[LIM], ile[LIM];
int n, m;
int fndl(int x) {
if(Fl[x]==x) return x;
return Fl[x]=fndl(Fl[x]);
}
void unil(int a, int b) {
a=fndl(a);
b=fndl(b);
if(a==b) return;
Fl[b]=a;
V[a].pb(b);
}
void DFS(int x) {
++lpre;
pocz[x]=lpre;
for(auto i : V[x]) {
nxt[i][0]=x;
DFS(i);
}
kon[x]=lpre;
}
int poddrzewo(int v, int l) {
for(int i=LG-1; i>=0; --i) if(nxt[v][i]>=l) v=nxt[v][i];
return v;
}
int fndr(int x) {
if(Fr[x]==x) return x;
return fndr(Fr[x]);
}
void unir(int a, int b) {
a=fndr(a);
b=fndr(b);
if(a==b) return;
if(ile[a]<ile[b]) swap(a, b);
for(auto i : zbior[b]) zbior[a].insert(i);
zbior[b].clear();
ile[a]+=ile[b];
Fr[b]=a;
}
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
n=N;
m=X.size();
rep(i, n) Fl[i]=i;
rep(i, m) {
if(X[i]>Y[i]) swap(X[i], Y[i]);
kraw.pb({X[i], Y[i]});
}
sort(all(kraw));
reverse(all(kraw));
for(auto i : kraw) unil(i.st, i.nd);
DFS(0);
for(int j=1; j<LG; ++j) {
rep(i, n) nxt[i][j]=nxt[nxt[i][j-1]][j-1];
}
rep(i, S.size()) pytania[R[i]].pb(i);
vi ans(S.size());
rep(i, n) {
Fr[i]=i;
ile[i]=1;
zbior[i].insert(pocz[i]);
}
rep(i, m) dodaj[kraw[i].nd].pb(kraw[i].st);
rep(i, n) {
for(auto j : dodaj[i]) unir(i, j);
for(auto j : pytania[i]) {
int p=poddrzewo(S[j], L[j]);
int x=fndr(E[j]);
auto it=zbior[x].lower_bound(pocz[p]);
if(it==zbior[x].end()) continue;
auto a=*it;
if(a<=kon[p]) ans[j]=1;
}
}
return ans;
}
