#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
struct KRT {
int N, LOG;
vector<vector<int>> child;
vector<int> parent; // parent in KRT, 0 = super-root
vector<int> tin, tout; // Euler tin/tout for vertices 1..N
vector<int> euler; // euler[t] = vertex at time t, t in 1..N
vector<vector<int>> up; // binary lifting
KRT(int n = 0) { init(n); }
void init(int n) {
N = n;
child.assign(N + 1, {});
parent.assign(N + 1, 0);
tin.assign(N + 1, 0);
tout.assign(N + 1, 0);
euler.assign(N + 1, 0);
LOG = 1;
while ((1 << LOG) <= N) ++LOG;
up.assign(LOG, vector<int>(N + 1, 0));
}
void build_lift() {
for (int i = 1; i <= N; ++i) up[0][i] = parent[i];
for (int k = 1; k < LOG; ++k) {
for (int i = 1; i <= N; ++i) {
up[k][i] = up[k - 1][ up[k - 1][i] ];
}
}
}
// iterative DFS from super-root 0; assigns tin/tout for all vertices 1..N
void build_euler() {
int timer = 0;
vector<int> it(N + 1, 0);
vector<int> st;
st.push_back(0);
while (!st.empty()) {
int u = st.back();
if (u != 0 && it[u] == 0) {
tin[u] = ++timer;
euler[timer] = u;
}
if (it[u] < (int)child[u].size()) {
int v = child[u][it[u]++];
st.push_back(v);
} else {
if (u != 0) tout[u] = timer;
st.pop_back();
}
}
}
};
static KRT build_left_krt(int N, const vector<vector<int>>& adj) {
KRT krt(N);
vector<int> dsu(N + 1), active(N + 1, 0), stamp(N + 1, 0);
auto find_set = [&](auto&& self, int v) -> int {
if (dsu[v] == v) return v;
return dsu[v] = self(self, dsu[v]);
};
for (int i = 1; i <= N; ++i) dsu[i] = i;
for (int i = N; i >= 1; --i) {
active[i] = 1;
dsu[i] = i;
vector<int> reps;
for (int j : adj[i]) if (active[j]) {
int r = find_set(find_set, j);
if (r == i) continue;
if (stamp[r] != i) {
stamp[r] = i;
reps.push_back(r);
}
}
for (int r : reps) {
krt.child[i].push_back(r);
krt.parent[r] = i;
}
for (int r : reps) dsu[r] = i;
}
// connect component roots to super-root 0
for (int v = 1; v <= N; ++v) {
int r = find_set(find_set, v);
if (r == v && krt.parent[v] == 0) {
krt.child[0].push_back(v);
krt.parent[v] = 0;
}
}
krt.build_euler();
krt.build_lift();
return krt;
}
static KRT build_right_krt(int N, const vector<vector<int>>& adj) {
KRT krt(N);
vector<int> dsu(N + 1), active(N + 1, 0), stamp(N + 1, 0);
auto find_set = [&](auto&& self, int v) -> int {
if (dsu[v] == v) return v;
return dsu[v] = self(self, dsu[v]);
};
for (int i = 1; i <= N; ++i) dsu[i] = i;
for (int i = 1; i <= N; ++i) {
active[i] = 1;
dsu[i] = i;
vector<int> reps;
for (int j : adj[i]) if (active[j]) {
int r = find_set(find_set, j);
if (r == i) continue;
if (stamp[r] != i) {
stamp[r] = i;
reps.push_back(r);
}
}
for (int r : reps) {
krt.child[i].push_back(r);
krt.parent[r] = i;
}
for (int r : reps) dsu[r] = i;
}
// connect component roots to super-root 0
for (int v = 1; v <= N; ++v) {
int r = find_set(find_set, v);
if (r == v && krt.parent[v] == 0) {
krt.child[0].push_back(v);
krt.parent[v] = 0;
}
}
krt.build_euler();
krt.build_lift();
return krt;
}
static int lift_left(const KRT& krt, int u, int L) {
for (int k = krt.LOG - 1; k >= 0; --k) {
int a = krt.up[k][u];
if (a != 0 && a >= L) u = a;
}
return u;
}
static int lift_right(const KRT& krt, int u, int R) {
for (int k = krt.LOG - 1; k >= 0; --k) {
int a = krt.up[k][u];
if (a != 0 && a <= R) u = a;
}
return u;
}
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)
{
int M = (int)X.size();
int Q = (int)S.size();
// IOI werewolf is 0-based (0..N-1). Shift to 1-based internally if it looks 0-based.
int mx = -1;
auto upd_mx = [&](const vector<int>& a){ for (int v: a) mx = max(mx, v); };
upd_mx(X); upd_mx(Y); upd_mx(S); upd_mx(E); upd_mx(L); upd_mx(R);
if (mx <= N - 1) {
for (int &v : X) ++v;
for (int &v : Y) ++v;
for (int &v : S) ++v;
for (int &v : E) ++v;
for (int &v : L) ++v;
for (int &v : R) ++v;
}
vector<vector<int>> adj(N + 1);
for (int i = 0; i < M; ++i) {
int a = X[i], b = Y[i];
adj[a].push_back(b);
adj[b].push_back(a);
}
KRT left = build_left_krt(N, adj);
KRT right = build_right_krt(N, adj);
// BIT over left Euler positions
vector<int> bit(N + 1, 0);
auto bit_add = [&](int pos) {
for (; pos <= N; pos += pos & -pos) bit[pos] += 1;
};
auto bit_sum = [&](int pos) {
int r = 0;
for (; pos > 0; pos -= pos & -pos) r += bit[pos];
return r;
};
auto bit_query = [&](int l, int r) {
if (l > r) return 0;
return bit_sum(r) - bit_sum(l - 1);
};
vector<vector<int>> evL(N + 1), evR(N + 1);
vector<int> l1(Q, 0), r1(Q, -1), l2(Q, 0), r2(Q, -1);
vector<int> ans(Q, 0);
for (int i = 0; i < Q; ++i) {
int s = S[i], e = E[i], l = L[i], r = R[i];
// necessary condition (phases): start must be >=L, end must be <=R
if (s < l || e > r) { ans[i] = 0; continue; }
int u = lift_left(left, s, l); // component(S) in induced >=L
int v = lift_right(right, e, r); // component(E) in induced <=R
l1[i] = left.tin[u];
r1[i] = left.tout[u];
l2[i] = right.tin[v];
r2[i] = right.tout[v];
evR[r2[i]].push_back(i);
evL[l2[i] - 1].push_back(i); // l2>=1 always (all nodes visited)
}
// sweep t = 0..N: maintain prefix of right Euler, mark their positions in left Euler
for (int t = 0; t <= N; ++t) {
if (t >= 1) {
int x = right.euler[t];
bit_add(left.tin[x]);
}
for (int id : evL[t]) ans[id] -= bit_query(l1[id], r1[id]);
for (int id : evR[t]) ans[id] += bit_query(l1[id], r1[id]);
}
for (int i = 0; i < Q; ++i) ans[i] = (ans[i] > 0 ? 1 : 0);
return ans;
}
