#include "werewolf.h"
#include <bits/stdc++.h>
#ifndef LOCAL
#define cerr if(false)cerr
#endif
using namespace std;
using ll = long long;
const int MAXN = 1e6 + 11;
int N, Q, M;
int P[MAXN], sz, par[MAXN], val[MAXN], go[MAXN][2];
int getP(int a) {
if (a == P[a]) return a;
return P[a] = getP(P[a]);
}
vector<int>g[MAXN];
int L[MAXN], R[MAXN];
vector<int>G[2];
void dfs(int v, int t) {
if (!go[v][0] && !go[v][1]) {
L[v] = R[v] = G[t].size();
cerr << v << " " << t << " " << L[v] << " " << R[v] << endl;
G[t].emplace_back(v);
return;
}
dfs(go[v][0], t);
dfs(go[v][1], t);
L[v] = L[go[v][0]];
R[v] = R[go[v][1]];
cerr << v << " " << t << " " << L[v] << " " << R[v] << endl;
}
vector<int> check_validity(int N_, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> Lq, vector<int> Rq) {
N = N_;
M = X.size();
Q = S.size();
for (int i = 0 ; i < M ; ++ i) {
g[X[i]].emplace_back(Y[i]);
g[Y[i]].emplace_back(X[i]);
}
sz = N;
for (int i = 0 ; i < N ; ++ i) P[i] = i;
for (int i = 0 ; i < N ; ++ i) {
for (int j : g[i]) if (j < i) {
int x = getP(i);
int y = getP(j);
if (x != y) {
P[x] = P[y] = P[sz] = sz;
go[sz][0] = x, go[sz][1] = y;
par[x] = par[y] = sz;
val[sz] = i;
sz++;
}
}
}
dfs(sz-1, 0);
int off = sz;
for (int i = 0 ; i < N ; ++ i) P[i+off] = i+off;
sz += N;
for (int i = N-1 ; i >= 0 ; -- i) {
for (int j : g[i]) if (j > i) {
int x = getP(i+off);
int y = getP(j+off);
if (x != y) {
P[x] = P[y] = P[sz] = sz;
go[sz][0] = x, go[sz][1] = y;
par[x] = par[y] = sz;
val[sz] = i;
sz++;
}
}
}
dfs(sz-1, 1);
for (int &i : G[1]) i -= off;
for (int i : G[0]) cerr << i << " ";
cerr << ": G[0]\n";
for (int i : G[1]) cerr << i << " ";
cerr << ": G[1]\n";
vector<int>ANS(Q);
for (int q = 0 ; q < Q ; ++ q) {
int Ls, Rs, Le, Re;
{
int v = E[q];
while (par[v] && val[par[v]] <= Rq[q]) v = par[v];
Le = L[v], Re = R[v];
}
{
int v = S[q] + off;
while (par[v] && val[par[v]] >= Lq[q]) v = par[v];
Ls = L[v], Rs = R[v];
}
cerr << Ls << " " << Rs << " " << Le << " " << Re << " LR" << endl;
bool has = false;
for (int i = Le ; i <= Re ; ++ i) {
for (int j = Ls ; j <= Rs ; ++ j) {
if (G[0][i] == G[1][j]) {
has = true;
}
}
}
ANS[q] = has;
}
return ANS;
}
