#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 = 2e3+5;
vector <vii> g(M),v(M);
int par[M];
int cur;
int in1[M],out1[M];
int in2[M],out2[M];
int x[M],y[M];
pii Lr[M],Rr[M];
int px[M],py[M];
int Arr[M];
int up1[20][M],up2[20][M];
vector <vii> t(M*4);
void cleardsu() {
cur = 0;
for (int i = 0; i < M; i++) {
par[i] = i;
v[i].clear();
}
}
int getpar(int x) {
if (x == par[x]) return x;
return par[x] = getpar(par[x]);
}
void unionset(int a, int b) {
a = getpar(a);
b = getpar(b);
if (b == a) return;
par[b] = a;
v[a].pb(b);
v[b].pb(a);
}
void dfs1(int x, int p) {
in1[x] = ++cur;
up1[0][x] = p;
for (int i = 1; i <= 18; i++) {
up1[i][x] = up1[i-1][up1[i-1][x]];
}
for (auto to:v[x]) {
if (to == p) continue;
dfs1(to,x);
}
out1[x] = cur;
}
void dfs2(int x, int p) {
in2[x] = ++cur;
up2[0][x] = p;
for (int i = 1; i <= 18; i++) {
up2[i][x] = up2[i-1][up2[i-1][x]];
}
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) {
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) {
unionset(i,to);
}
}
}
dfs1(0,0);
for (int i = 0; i < N; i++) {
x[in1[i]] = i;
}
cleardsu();
for (int i = 0; i < N; i++) {
for (auto to:g[i]) {
if (to <= i) {
unionset(i,to);
}
}
}
dfs2(N-1,N-1);
for (int i = 0; i < N; i++) {
y[in2[i]] = i;
}
cleardsu();
for (int i = 0; i < N; i++) {
px[x[i]] = i;
}
for (int i = 0; i < N; i++) {
py[y[i]] = i;
}
for (int i = 0; i < N; i++) {
Arr[px[i]] = py[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] >= L[q]) st = up1[i][st];
}
for (int i = 18; i >= 0; i--) {
if (up2[i][ed] <= R[q]) ed = up2[i][ed];
}
int lx = in1[st];
int rx = out1[st];
int ly = in2[ed];
int ry = out2[ed];
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;
}
