#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
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 q = S.size(), cur = 0;
vector<vector<int>> G(n);
vector<int> id(n), ans(q), tin[2], tout[2], subtree[2], y(n + 1), bit(n + 1);
iota(id.begin(), id.end(), 0);
for (int i = 0; i < X.size(); ++i)
G[X[i]].emplace_back(Y[i]), G[Y[i]].emplace_back(X[i]);
for (const auto& [l, s] : {make_tuple(L,S),make_tuple(R,E)}) {
tin[cur].resize(n + 1), tout[cur].resize(n + 1), subtree[cur].resize(n + 1);
reverse(id.begin(), id.end());
vector<vector<int>> GT(n);
vector<vector<pair<int, int>>> Q(n);
for (int i = 0; i < q; ++i)
Q[l[i]].emplace_back(s[i], i);
vector<int> seen(n), p(n);
iota(p.begin(), p.end(), 0);
function<int(int)> get = [&](int x) {
if (p[x] == x)
return x;
return p[x] = get(p[x]);
};
int t = 0;
for (auto i : id) {
for (auto x : G[i])
if (seen[x] && (x = get(x)) != i) {
p[x] = i;
GT[i].emplace_back(x), GT[x].emplace_back(i);
}
for (auto [pos, nr] : Q[i])
subtree[cur][nr] = get(pos);
seen[i] = 1;
}
function<void(int, int)> dfs = [&](int node, int last) {
tin[cur][node] = ++t;
for (auto x : GT[node])
if (x != last)
dfs(x, node);
tout[cur][node] = t;
};
dfs(id.back(), -1);
++cur;
}
for (int i = 0; i < n; ++i)
y[tin[0][i]] = tin[1][i];
auto update = [&](int pos) {
for (int i = pos; i <= n; i += i & -i)
++bit[i];
};
auto query = [&](int pos) {
int ans = 0;
for (int i = pos; i; i -= i & -i)
ans += bit[i];
return ans;
};
vector<vector<pair<int, int>>> Q(n+1);
for (int i = 0; i < q; ++i)
Q[tin[0][subtree[0][i]] - 1].emplace_back(i, -1),
Q[tout[0][subtree[0][i]]].emplace_back(i, 1);
for (int i = 1; i <= n; ++i) {
update(y[i]);
for (auto [nr, sgn] : Q[i])
ans[nr] += sgn * (query(tout[1][subtree[1][nr]]) - query(tin[1][subtree[1][nr]] - 1));
}
for (int i = 0; i < q; ++i)
ans[i] = !!ans[i];
return ans;
}
