#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
int N, timer;
vector<int> a[2], l[2], r[2], p[2];
vector<vector<int>> adj[2], ch[2];
void dfs(int z, int x) {
l[z][x] = timer;
for (int y : ch[z][x]) {
dfs(z, y);
}
r[z][x] = ++timer;
a[z].push_back(x);
}
void build(int z) {
p[z].resize(N, N);
l[z].resize(N);
r[z].resize(N);
ch[z].resize(N);
vector<int> par(N);
iota(par.begin(), par.end(), 0);
function<int(int)> find = [&](int x) {
return x == par[x] ? x : par[x] = find(par[x]);
};
for (int i = 0; i < N; i++) {
for (int j : adj[z][i]) {
if (j < i) {
int x = find(j);
if (x != i) {
ch[z][i].push_back(x);
p[z][x] = par[x] = i;
}
}
}
}
timer = 0;
dfs(z, N - 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) {
N = n;
adj[0].resize(N);
adj[1].resize(N);
for (int i = 0; i < X.size(); i++) {
adj[0][X[i]].push_back(Y[i]);
adj[0][Y[i]].push_back(X[i]);
X[i] = N - 1 - X[i];
Y[i] = N - 1 - Y[i];
adj[1][X[i]].push_back(Y[i]);
adj[1][Y[i]].push_back(X[i]);
}
build(0);
build(1);
for (int i = 0; i < N; i++) {
a[1][i] = N - 1 - a[1][i];
p[1][i] = N - 1 - p[1][i];
for (int &x : ch[1][i]) {
x = N - 1 - x;
}
}
for (int i = 0; i < N / 2; i++) {
swap(p[1][i], p[1][N - 1 - i]);
swap(l[1][i], l[1][N - 1 - i]);
swap(r[1][i], r[1][N - 1 - i]);
swap(ch[1][i], ch[1][N - 1 - i]);
}
int par[2][N][18];
for (int i = 0; i < N; i++) {
for (int j = 0; j < 18; j++) {
par[0][i][j] = N;
par[1][i][j] = -1;
}
}
for (int i = N - 1; i >= 0; i--) {
par[0][i][0] = p[0][i];
for (int j = 0; j < 17 && par[0][i][j] != N; j++) {
par[0][i][j + 1] = par[0][par[0][i][j]][j];
}
}
for (int i = 0; i < N; i++) {
par[1][i][0] = p[1][i];
for (int j = 0; j < 17 && par[1][i][j] != -1; j++) {
par[1][i][j + 1] = par[1][par[1][i][j]][j];
}
}
int Q = S.size();
vector<int> ans(Q), L0(Q), R0(Q), L1(Q), R1(Q);
vector<vector<int>> T(N);
for (int i = 0; i < Q; i++) {
int t[2];
t[0] = E[i];
for (int j = 17; j >= 0; j--) {
if (par[0][t[0]][j] <= R[i]) {
t[0] = par[0][t[0]][j];
}
}
t[1] = S[i];
for (int j = 17; j >= 0; j--) {
if (par[1][t[1]][j] >= L[i]) {
t[1] = par[1][t[1]][j];
}
}
L0[i] = l[0][t[0]];
R0[i] = r[0][t[0]];
L1[i] = l[1][t[1]];
R1[i] = r[1][t[1]];
T[R1[i] - 1].push_back(i);
}
vector<int> b(N);
for (int i = 0; i < N; i++) {
b[a[0][i]] = i;
}
vector<int> st(2 * N, -1);
for (int i = 0; i < N; i++) {
int j = b[a[1][i]];
for (st[j += N] = i; j /= 2;) {
st[j] = max(st[j * 2], st[j * 2 + 1]);
}
for (int j : T[i]) {
int k = -1, l = L0[j], r = R0[j];
for (l += N, r += N; l < r; l /= 2, r /= 2) {
if (l % 2 == 1) {
k = max(k, st[l++]);
}
if (r % 2 == 1) {
k = max(k, st[--r]);
}
}
ans[j] = k >= L1[j];
}
}
return ans;
}
