#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
const int N = 4e5 + 5, L = 20;
int w[N], tin[2][N], tout[2][N], p[2][N][L], t[N];
vector<int> g[N], tr[2][N];
int timer;
struct E {
int t, x, y, i, k;
};
void upd(int x, int y) {
for (; x < N; x |= x + 1)
t[x] += y;
}
int que(int x) {
int s = 0;
for (; x >= 0; x = (x & (x + 1)) - 1)
s += t[x];
return s;
}
int findSet(int v) {
return w[v] < 0 ? v : w[v] = findSet(w[v]);
}
void connect(int a, int b, int type) {
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]);
vector<E> ev;
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[1][v2][j] <= r[i]) {
v2 = p[1][v2][j];
}
}
ev.push_back({ tout[0][v1], tin[1][v2], tout[1][v2], i, 1 });
ev.push_back({ tin[0][v1] - 1, tin[1][v2], tout[1][v2], i, -1 });
}
for (int i = 0; i < n; i++) {
ev.push_back({ tin[0][i], tin[1][i], -1, -1 });
}
sort(all(ev), [](E a, E b) {
return a.t == b.t ? a.i == -1 : a.t < b.t;
});
for (E e : ev) {
if (e.i == -1) {
upd(e.x, 1);
}
else {
ans[e.i] += (que(e.y) - que(e.x - 1)) * e.k;
}
}
for (int i = 0; i < q; i++)
ans[i] = ans[i] > 0;
return ans;
}
