#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct DSU {
vector<int> par, sz, tin, tout;
vector<vector<int>> g;
int typ;
void init (int x, int y) {
typ = y;
par.assign(x + 2, -1);
sz.assign(x + 2, 1);
g.assign(x + 2, {});
tin.assign(x + 2, 0);
tout.assign(x + 2, 0);
}
int get_par (int x) {
if (par[x] == -1) return x;
return par[x] = get_par(par[x]);
}
bool add (int a, int b) {
a = get_par(a);
b = get_par(b);
if (a == b) return false;
if ((typ == 0 && a >= b) || (typ == 1 && a <= b)) swap(a, b);
par[b] = a;
g[a].push_back(b);
return true;
}
};
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 M = X.size(), Q = S.size();
vector<int> g[N];
for (int i = 0;i < M;i ++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
DSU DS[2];
DS[0].init(N, 0);
DS[1].init(N, 1);
vector<array<int, 2>> ind(Q, {0, 0});
{
vector<int> _g1[N], _g2[N];
for (int i = 0;i < Q;i ++) {
_g1[L[i]].push_back(i);
_g2[R[i]].push_back(i);
}
for (int i = N - 1;i >= 0;i --) {
for (auto j : g[i]) {
if (j > i) {
DS[0].add(i, j);
}
}
for (auto j : _g1[i]) {
ind[j][0] = DS[0].get_par(S[j]);
}
}
for (int i = 0;i < N;i ++) {
for (auto j : g[i]) {
if (j < i) {
DS[1].add(i, j);
}
}
for (auto j : _g2[i]) {
ind[j][1] = DS[1].get_par(E[j]);
}
}
}
int _time;
function<void(int, int)> dfs_init = [&](int si, int typ) -> void {
DS[typ].tin[si] = ++ _time;
for (auto ti : DS[typ].g[si]) {
dfs_init(ti, typ);
}
DS[typ].tout[si] = _time;
};
for (int i = 0;i < 2;i ++) {
_time = -1;
dfs_init(DS[i].get_par(0), i);
}
vector<int> _g[N];
for (int i = 0;i < Q;i ++) {
_g[ind[i][0]].push_back(i);
}
set<int> sl[N];
vector<int> res(Q);
function<void(int)> dfs = [&](int si) -> void {
sl[si].insert(DS[1].tin[si]);
for (auto ti : DS[0].g[si]) {
dfs(ti);
if (sl[si].size() < sl[ti].size()) {
swap(sl[si], sl[ti]);
}
for (auto x : sl[ti]) {
sl[si].insert(x);
}
sl[ti].clear();
}
for (auto ti : _g[si]) {
int l = DS[1].tin[ind[ti][1]], r = DS[1].tout[ind[ti][1]];
res[ti] = (sl[si].lower_bound(l) != sl[si].upper_bound(r));
}
};
dfs(0);
return res;
}
