#include "werewolf.h"
#include<algorithm>
#include<vector>
#define N_ 201000
#define M_ 401000
using namespace std;
int n, m, Q, UF[N_], par[N_][2][20], Num[N_][2], Ed[N_][2], cnt, ReNum[N_][2];
vector<int> UU[N_], DD[N_];
vector<int> T[N_][2];
int Find(int a) {
if (a == UF[a])return a;
return UF[a] = Find(UF[a]);
}
void DFS(int a, int ck) {
Num[a][ck] = ++cnt;
ReNum[cnt][ck] = a;
for (auto &x : T[a][ck]) {
par[x][ck][0] = a;
DFS(x, ck);
}
Ed[a][ck] = cnt;
}
struct PST {
int l, r, s;
}IT[N_*20];
int Root[N_], cc;
void Put(int rt, int cur, int b, int e, int x) {
IT[cur] = IT[rt];
if (b == e) {
IT[cur].s++;
return;
}
int m = (b + e) >> 1;
cc++;
if (x <= m) {
IT[cur].l = cc;
Put(IT[rt].l, IT[cur].l, b, m, x);
}
else {
IT[cur].r = cc;
Put(IT[rt].r, IT[cur].r, m + 1, e, x);
}
IT[cur].s = IT[IT[cur].l].s + IT[IT[cur].r].s;
}
int Sum(int nd, int b, int e, int s, int l) {
if (b == s && e == l)return IT[nd].s;
int m = (b + e) >> 1, r = 0;
if (s <= m) r += Sum(IT[nd].l, b, m, s, min(m, l));
if (l > m)r += Sum(IT[nd].r, m + 1, e, max(m + 1, s), l);
return r;
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
n = N;
m = X.size();
Q = S.size();
int i, j;
for (i = 0; i < n; i++)UF[i] = i;
for (i = 0; i < m; i++) {
int x = X[i], y = Y[i];
if (x > y)swap(x, y);
UU[x].push_back(y);
DD[y].push_back(x);
}
for (i = 0; i < n; i++) {
for (auto &x : DD[i]) {
int y = Find(x);
if (y == i)continue;
T[i][0].push_back(y);
UF[y] = i;
}
}
for (i = 0; i < n; i++)UF[i] = i;
for (i = n - 1; i >= 0; i--) {
for (auto &x : UU[i]) {
int y = Find(x);
if (y == i)continue;
T[i][1].push_back(y);
UF[y] = i;
}
}
cnt = 0;
DFS(n - 1, 0);
cnt = 0;
DFS(0, 1);
par[n - 1][0][0] = n - 1;
par[0][1][0] = 0;
for (i = 0; i < 18; i++) {
for (j = 0; j < n; j++) {
par[j][0][i + 1] = par[par[j][0][i]][0][i];
par[j][1][i + 1] = par[par[j][1][i]][1][i];
}
}
for (i = 1; i <= n; i++) {
Root[i] = ++cc;
int x = ReNum[i][0];
Put(Root[i - 1], Root[i], 1, n, Num[x][1]);
}
vector<int>ret;
for (i = 0; i < Q; i++) {
int x = S[i], y = E[i];
for (j = 18; j >= 0; j--) {
if (par[x][1][j] >= L[i])x = par[x][1][j];
if (par[y][0][j] <= R[i])y = par[y][0][j];
}
if (Sum(Root[Ed[y][0]], 1, n, Num[x][1], Ed[x][1]) - Sum(Root[Num[y][0] - 1], 1, n, Num[x][1], Ed[x][1]) > 0)ret.push_back(1);
else ret.push_back(0);
}
return ret;
}
