/* In the name of GOD */
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200012;
vector <int> g[N], t[2][N * 2];
int p[N * 2];
int par[2][N * 2];
int q;
int n;
int m;
int sz = N;
bool vis[N * 2];
void clear () {
sz = N;
for (int i = 0; i < N * 2; i++)
p[i] = i;
}
int get_par (int v) {
return (p[v] == v ? v : p[v] = get_par (p[v]));
}
void merge (int u, int v, int i) {
u = get_par (u);
v = get_par (v);
if (u == v)
return;
sz++;
p[u] = sz;
p[v] = sz;
t[i][sz].push_back(v);
t[i][sz].push_back(u);
}
struct que {
int s, e, l, r;
int v1, v2;
} qu[N];
vector <int> ll[N], rr[N];
int st [2][N * 2], ft [2][N * 2];
int ti = 1;
void dfs (int v, int i) {
vis[v] = true;
st[i][v] = ti;
for (int u : t[i][v])
dfs (u, i);
if (v < N)
ti++;
ft[i][v] = ti;
}
std::vector<int> check_validity(int NN, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
q = S.size();
n = NN;
m = X.size();
for (int i = 0; i < m; i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
for (int i = 0; i < q; i++) {
qu[i].s = S[i];
qu[i].e = E[i];
qu[i].l = L[i];
qu[i].r = R[i];
ll[L[i]].push_back(i);
rr[R[i]].push_back(i);
}
clear();
for (int i = 0; i < n; i++) {
for (int j : g[i]) {
if (j < i)
merge (i, j, 0);
}
for (int j : rr[i]) {
qu[j].v1 = get_par (qu[j].e);
}
}
clear();
for (int i = n - 1; i >= 0; i--) {
for (int j : g[i])
if (j > i)
merge (i, j, 1);
for (int j : ll[i]) {
qu[j].v2 = get_par (qu[j].s);
}
}
for (int i = 2 * N - 1; i >= N; i--) {
if (!vis[i] && !t[0][i].empty()) {
dfs (i, 0);
}
}
ti = 1;
for (int i = 0; i < 2 * N; i++)
vis[i] = false;
for (int i = 2 * N - 1; i >= N; i--) {
if (!vis[i] && !t[1][i].empty()) {
dfs (i, 1);
}
}
for (int i = 0; i < 2 * N; i++) {
ft[0][i]--;
ft[1][i]--;
}
vector <int> wef;
for (int i = 0; i < q; i++) {
int f = 0;
for (int j = 0; j < n; j++) {
if (st[0][qu[i].v1] <= st[0][j] && st[0][j] <= ft[0][qu[i].v1]) {
if (st[1][qu[i].v2] <= st[1][j] && st[1][j] <= ft[1][qu[i].v2]) {
f = true;
}
}
}
wef.push_back(f);
}
return wef;
}
