#include "werewolf.h"
using namespace std;
#define ll long long
const int N = 4e5 + 5, L = 20;
int w[N], tin[2][N], tout[2][N], p[2][N][L];
vector<int> g[N], tr[2][N];
int timer;
int findSet(int v) {
return w[v] < 0 ? v : w[v] = findSet(w[v]);
}
void connect(int a, int b, int type) {
if (a > b)
swap(a, b);
a = findSet(a);
b = findSet(b);
if (a != b) {
w[a] += w[b];
w[b] = a;
tr[type][a].push_back(b);
}
}
void dfs(int node, int p[N][L], int tin[N], int tout[N], vector<int> tr[N]) {
tin[node] = ++timer;
for (int i = 1; i < L; i++) {
p[node][i] = p[p[node][i - 1]][i - 1];
}
for (int to : tr[node]) {
p[to][0] = node;
dfs(to, p, tin, tout, tr);
}
tout[node] = timer;
}
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(), m = x.size();
vector<int> ans(q);
for (int i = 0; i < m; i++) {
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
fill(w, w + n, -1);
for (int i = n - 1; i >= 0; i--) {
for (int to : g[i]) {
if (to > i) {
connect(i, to, 0);
}
}
}
fill(w, w + n, -1);
for (int i = 0; i < n; i++) {
for (int to : g[i]) {
if (to < i) {
connect(i, to, 1);
}
}
}
timer = -1;
dfs(0, p[0], tin[0], tout[0], tr[0]);
timer = -1;
fill(p[1][n - 1], p[1][n - 1] + L, n - 1);
dfs(n - 1, p[1], tin[1], tout[1], tr[1]);
for (int i = 0; i < q; i++) {
int v1 = s[i], v2 = e[i];
for (int j = L - 1; j >= 0; j--) {
if (p[0][v1][j] >= l[i]) {
v1 = p[0][v1][j];
}
}
for (int j = L - 1; j >= 0; j--) {
if (p[0][v2][j] <= r[i]) {
v2 = p[1][v2][j];
}
}
for (int j = l[i]; j <= r[i]; j++) {
if (tin[0][j] >= tin[0][v1] && tin[0][j] <= tout[0][v1] &&
tin[1][j] >= tin[1][v2] && tin[1][j] <= tout[1][v2]) {
ans[i] = 1;
}
}
}
return ans;
}
