#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
typedef vector<int> vii;
typedef pair<int, int> pii;
const int M = 2e5+5;
vector <vii> g,v;
int par[M];
int cur;
int in1[M],out1[M];
int in2[M],out2[M];
int Arr[M];
int up1[20][M],up2[20][M];
int vis[M];
int n;
vector <vii> t;
void cleardsu() {
cur = 0;
for (int i = 0; i < n; i++) {
vis[i] = 0;
par[i] = i;
v[i].clear();
}
}
int getpar(int x) {
if (x == par[x]) return x;
return par[x] = getpar(par[x]);
}
void dfs1(int x, int p) {
vis[x] = 1;
in1[x] = cur++;
up1[0][x] = p;
for (int i = 1; i <= 18; i++) {
if (up1[i-1][x] != -1) up1[i][x] = up1[i-1][up1[i-1][x]]; else up1[i][x] = -1;
}
for (auto to:v[x]) {
if (to == p) continue;
dfs1(to,x);
}
out1[x] = cur;
}
void dfs2(int x, int p) {
vis[x] =1;
in2[x] = cur++;
up2[0][x] = p;
for (int i = 1; i <= 18; i++) {
if (up2[i-1][x] != -1) up2[i][x] = up2[i-1][up2[i-1][x]]; else up2[i][x] = -1;
}
for (auto to:v[x]) {
if (to == p) continue;
dfs2(to,x);
}
out2[x] = cur;
}
vii merge(vii a, vii b) {
vii res;
int pos1 = 0;
int pos2 = 0;
while (pos1 < sz(a) && pos2 < sz(b)) {
if (a[pos1] < b[pos2]) {
res.pb(a[pos1]);
pos1++;
} else {
res.pb(b[pos2]);
pos2++;
}
}
while (pos2 < sz(b)) {
res.pb(b[pos2]);
pos2++;
}
while (pos1 < sz(a)) {
res.pb(a[pos1]);
pos1++;
}
return res;
}
void build(int node, int l, int r) {
if (l == r) {
t[node].pb(Arr[l]);
return;
}
int mid = (l+r)/2;
build (node*2,l,mid);
build(node*2+1,mid+1,r);
t[node] = merge(t[node*2],t[node*2+1]);
}
bool getans(int node, int l, int r, int lx, int rx, int ly, int ry) {
if (r < lx || l > rx) return 0;
if (l >= lx && r <= rx) {
auto it = lower_bound(all(t[node]),ly);
return (it != t[node].end() && *it <= ry);
}
int mid = (l+r)/2;
return (getans(node*2,l,mid,lx,rx,ly,ry) || getans(node*2+1,mid+1,r,lx,rx,ly,ry));
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
t.resize(N*4);
g.resize(N);
v.resize(N);
n= N;
int Q = S.size();
vector<int> A(Q);
for (int i = 0; i < Q; ++i) {
A[i] = 0;
}
for (int i = 0; i < sz(X); i++) {
g[X[i]].pb(Y[i]);
g[Y[i]].pb(X[i]);
}
cleardsu();
for (int i = N-1; i >= 0; i--) {
for (auto to: g[i]) {
if (to >= i) {
int a = getpar(to);
if (a != i) {
par[a] = i;
v[i].pb(a);
}
}
}
}
for (int i = 0; i < N; i++) {
if (!vis[getpar(i)]) {
dfs1(getpar(i),-1);
}
}
cleardsu();
for (int i = 0; i < N; i++) {
for (auto to:g[i]) {
if (to <= i) {
int a = getpar(to);
if (a != i) {
par[a] = i;
v[i].pb(a);
}
}
}
}
for (int i = 0; i < N; i++) {
if (!vis[getpar(i)]) {
dfs2(getpar(i),-1);
}
}
cleardsu();
for (int i = 0; i < N; i++) {
Arr[in1[i]] = in2[i];
}
build (1,0,N-1);
int q = 0;
while (q < Q) {
int st = S[q];
int ed = E[q];
for (int i = 18; i >= 0; i--) {
if (up1[i][st] != -1 && up1[i][st] >= L[q]) st = up1[i][st];
}
for (int i = 18; i >= 0; i--) {
if (up2[i][ed] != -1 && up2[i][ed] <= R[q]) ed = up2[i][ed];
}
int lx = in1[st];
int rx = out1[st]-1;
int ly = in2[ed];
int ry = out2[ed]-1;
if (st < L[q] || ed > R[q]) {
A[q] = 0;
q++;
continue;
}
A[q] = getans(1,0,N-1,lx,rx,ly,ry);
q++;
}
return A;
}
