#include "werewolf.h"
#include <bits/stdc++.h>
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> a, std::vector<int> b) {
int q = s.size(), m = x.size();
std::vector<int> pr(n);
std::function<int(int)> find = [&](int u) {
return u == pr[u] ? u : pr[u] = find(pr[u]);
};
std::vector<std::vector<int>> g(n), tr(n);
for (int i = 0; i < m; ++i) {
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
std::vector<int> ind(n), rank(n);
std::vector<std::vector<std::array<int, 2>>> at(n);
auto solve = [&](std::vector<int> &tin, std::vector<int> &tout, std::vector<int> &head) {
iota(pr.begin(), pr.end(), 0);
for (int i = 0; i < n; ++i) {
int u = ind[i];
for (int j : g[u]) {
if (rank[j] < i && (j = find(j)) != u) {
pr[j] = u;
tr[u].push_back(j);
}
}
for (auto [j, v] : at[u]) {
head[j] = find(v);
}
}
int timer = 0;
std::function<void(int)> dfs = [&](int u) {
tin[u] = ++timer;
for (int v : tr[u]) {
dfs(v);
}
tout[u] = timer;
};
dfs(ind.back());
};
std::vector tin(2, std::vector<int>(n)), tout(2, std::vector<int>(n)), head(2, std::vector<int>(q));
for (int i = 0; i < n; ++i) {
ind[i] = n - 1 - i;
rank[n - 1 - i] = i;
}
for (int i = 0; i < q; ++i) {
at[a[i]].push_back({i, s[i]});
}
solve(tin[0], tout[0], head[0]);
for (int i = 0; i < n; ++i) {
ind[i] = i;
rank[i] = i;
std::vector<int>().swap(tr[i]);
std::vector<std::array<int, 2>>().swap(at[i]);
}
for (int i = 0; i < q; ++i) {
at[b[i]].push_back({i, e[i]});
}
solve(tin[1], tout[1], head[1]);
std::vector<std::vector<std::array<int, 3>>> queries(n + 1);
std::vector<int> ft(n + 1);
for (int i = 0; i < q; ++i) {
std::array<std::array<int, 2>, 2> range;
for (int j = 0; j < 2; ++j) {
range[j] = {tin[j][head[j][i]], tout[j][head[j][i]]};
}
queries[range[0][0] - 1].push_back({range[1][0], range[1][1], -i - 1});
queries[range[0][1]].push_back({range[1][0], range[1][1], i + 1});
}
auto upd = [&](int i) {
for (; i <= n; i += i & -i) {
++ft[i];
}
};
auto qry = [&](int i) {
int cnt = 0;
for (; i; i -= i & -i) {
cnt += ft[i];
}
return cnt;
};
std::vector<int> res(q), pos(n + 1);
for (int i = 0; i < n; ++i) {
pos[tin[0][i]] = i;
}
for (int i = 1; i <= n; ++i) {
upd(tin[1][pos[i]]);
for (auto [l, r, id] : queries[i]) {
if (id > 0) {
res[id - 1] += qry(r) - qry(l - 1);
} else {
res[-1 - id] -= qry(r) - qry(l - 1);
}
}
}
for (int i = 0; i < q; ++i) {
res[i] = res[i] > 0;
}
return res;
}
