#pragma GCC optimize ("O3")
#include "werewolf.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct DSU {
int components;
vector<int>par;
DSU(int n) {
par.assign(n, -1);
components = n;
}
int Find(int u) {
if (par[u] < 0) return u;
else return par[u] = Find(par[u]);
}
bool Union(int u, int v) {
u = Find(u);
v = Find(v);
if (u != v) {
par[u] += par[v];
par[v] = u;
--components;
return true;
} else {
return false;
}
}
};
void dfs1(int node, vvi &tree, int &tmr, vi &tin, vi &tout) {
tin[node] = ++tmr;
for (int to : tree[node]) {
dfs1(to, tree, tmr, tin, tout);
}
tout[node] = tmr;
}
void dfs2(int node, vvi &tree, vi &tin, vi &tout, vvpii &group, vector<set<int>> &subTree, vi &res) {
int maxChild = -1;
for (int to : tree[node]) {
dfs2(to, tree, tin, tout, group, subTree, res);
if (maxChild == -1 || size(subTree[to]) > size(subTree[maxChild])) {
maxChild = to;
}
}
if (maxChild != -1) {
subTree[node] = subTree[maxChild];
for (int to : tree[node]) {
if (to != maxChild) {
subTree[node].insert(all(subTree[to]));
}
}
}
subTree[node].insert(tin[node]);
for (auto [v, i] : group[node]) {
auto itr = subTree[node].lower_bound(tin[v]);
if (itr != subTree[node].end() && (*itr) <= tout[v]) {
res[i] = 1;
}
}
}
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
int M = size(X);
vvi g(N);
for (int i = 0; i < M; ++i) {
g[X[i]].eb(Y[i]);
g[Y[i]].eb(X[i]);
}
DSU dsu1(N), dsu2(N);
vvi treeHuman(N), treeWolf(N);
vector<vvi>up(2, vvi(19, vi(N)));
up[0][0][0] = 0;
for (int i = N - 1; i >= 0; --i) {
for (int to : g[i]) {
if (to > i && dsu1.Find(to) != i) {
treeHuman[i].eb(dsu1.Find(to));
up[0][0][dsu1.Find(to)] = i;
dsu1.Union(i, to);
}
}
}
up[1][0][N - 1] = N - 1;
for (int i = 0; i < N; ++i) {
for (int to : g[i]) {
if (to < i && dsu2.Find(to) != i) {
treeWolf[i].eb(dsu2.Find(to));
up[1][0][dsu2.Find(to)] = i;
dsu2.Union(i, to);
}
}
}
for (int k = 0; k < 2; ++k) {
for (int i = 1; i < 19; ++i) {
for (int j = 0; j < N; ++j) {
up[k][i][j] = up[k][i - 1][up[k][i - 1][j]];
}
}
}
int Q = size(S);
vvpii group(N);
for (int i = 0; i < Q; ++i) {
for (int j = 18; j >= 0; --j) {
if (up[0][j][S[i]] >= L[i]) {
S[i] = up[0][j][S[i]];
}
if (up[1][j][E[i]] <= R[i]) {
E[i] = up[1][j][E[i]];
}
}
group[E[i]].eb(mpr(S[i], i));
}
int tmr = -1;
vi tin(N), tout(N);
dfs1(0, treeHuman, tmr, tin, tout);
vi res(Q, 0);
vector<set<int>>subTree(N);
dfs2(N - 1, treeWolf, tin, tout, group, subTree, res);
return res;
}
