#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
const int MAXN = (int) 5e5 + 5;
int n;
int t[MAXN];
void upd(int v, int val){
for(; v < MAXN; v += (v&-v))
t[v] += val;
}
int gt(int l, int r){
l--;
int res = 0;
for(; r; r -= (r&-r)) res += t[r];
for(; l; l -= (l&-l)) res -= t[l];
return res;
}
vector<pair<int, int>> Qs[MAXN];
vector<int> A;
struct ali{
int cev[MAXN], tin[MAXN], tout[MAXN], sz[MAXN], pari[MAXN][22];
int cur = 1;
int par[MAXN];
vector<int> adj[MAXN];
void ini(){
for(int i = 0; i < n; i++){
adj[i].clear();
sz[i] = 1;
par[i] = i;
pari[i][0] = i;
}
}
int find_set(int v){
if(par[v] == v) return v;
return par[v] = find_set(par[v]);
}
void merge(int a, int b, bool cr){
a = find_set(a);
b = find_set(b);
if(a == b) return;
if(cr){
if(a < b)
swap(a, b);
sz[a] += sz[b];
par[b] = a;
pari[b][0] = a;
adj[a].push_back(b);
}else{
if(a > b)
swap(a, b);
sz[a] += sz[b];
par[b] = a;
pari[b][0] = a;
adj[a].push_back(b);
}
}
void dfs(int v){
tin[v] = cur++;
cev[cur - 1] = v;
for(int l = 1; l < 22; l++)
pari[v][l] = pari[pari[v][l - 1]][l - 1];
for(int j: adj[v])
dfs(j);
tout[v] = cur - 1;
}
void dfs2(int v, bool keep, ali &s){
int hv = -1;
for(int j: adj[v])
if(hv == -1 || sz[j] > sz[hv])
hv = j;
for(int j: adj[v])
if(j != hv)
dfs2(j, 0, s);
if(hv != -1)
dfs2(hv, 1, s);
for(int j: adj[v])
if(j != hv)
for(int i = tin[j]; i <= tout[j]; i++)
upd(s.tin[cev[i]], 1);
upd(s.tin[v], 1);
for(auto j: Qs[v]){
int rs = gt(s.tin[j.first], s.tout[j.first]);
assert(rs >= 0);
A[j.second] = (rs != 0);
}
if(keep == 0)
for(int i = tin[v]; i <= tout[v]; i++)
upd(s.tin[cev[i]], -1);
}
} st1, st2;
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
n = N;
int M = X.size(), Q = S.size();
st1.ini();
st2.ini();
A.resize(Q);
vector<int> esi;
for(int i = 0; i < M; i++){
esi.push_back(i);
}
sort(esi.begin(), esi.end(), [&X, &Y](int a, int b){
if(min(X[a], Y[a]) == min(X[b], Y[b])){
return max(X[a], Y[a]) < max(X[b], Y[b]);
}
return min(X[a], Y[a]) > min(X[b], Y[b]);
});
st1.ini(); st2.ini();
for(int i = 0; i < M; i++){
st1.merge(X[esi[i]], Y[esi[i]], 0);
}
sort(esi.begin(), esi.end(), [&X, &Y](int a, int b){
if(max(X[a], Y[a]) == max(X[b], Y[b]))
return min(X[a], Y[a]) > min(X[b], Y[b]);
return max(X[a], Y[a]) < max(X[b], Y[b]);
});
for(int i = 0; i < M; i++){
st2.merge(X[esi[i]], Y[esi[i]], 1);
}
st1.dfs(0);
st2.dfs(n - 1);
for(int i = 0; i < Q; i++){
for(int j = 21; j >= 0; j--){
if(st1.pari[S[i]][j] >= L[i]){
S[i] = st1.pari[S[i]][j];
}
}
for(int j = 21; j >= 0; j--){
if(st2.pari[E[i]][j] <= R[i]){
E[i] = st2.pari[E[i]][j];
}
}
Qs[S[i]].push_back({E[i], i});
}
st1.dfs2(0, 1, st2);
return A;
}
