#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define NAME ""
#define ll long long
#define pii pair < int , int >
#define fi first
#define se second
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i ++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i --)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i ++)
#define bit(x, i) (((x) >> (i)) & 1ll)
#define mask(x) (1ll << (x))
#define mem(f, x) memset(f, x, sizeof(f))
#define sz(x) (int32_t) (x.size())
const int nmax = 2e5;
int timer = 0, in[2][nmax + 4], out[2][nmax + 4], top[2][nmax + 4], rev[nmax + 4];
vector < int > g[nmax + 4], adj[nmax + 4], ql[nmax + 4], qr[nmax + 4], op[nmax + 4], cl[nmax + 4];
struct DSU {
int par[nmax + 4];
void init(int n) {
iota(par, par + n, 0);
}
int find_par(int i) {
return (par[i] == i ? i : par[i] = find_par(par[i]));
}
bool unite(int u, int v) {
u = find_par(u);
v = find_par(v);
if (u == v) {
return 0;
}
par[v] = u;
adj[u].push_back(v);
return 1;
}
}dsu;
void dfs(int type, int i, int j) {
++ timer;
in[type][i] = timer;
for (auto x: adj[i]) {
// cout << i << " " << x << "\n";
if (x == j) {
continue;
}
dfs(type, x, i);
}
out[type][i] = timer;
}
struct SegTree {
int n, b[nmax * 4 + 4];
void init(int _n) {
n = _n;
}
void update(int id, int l, int r, int pos, int val) {
if (l == r) {
b[id] = val;
return;
}
int mid = l + r >> 1;
if (mid >= pos) {
update(id << 1, l, mid, pos, val);
}
else {
update(id << 1 | 1, mid + 1, r, pos, val);
}
b[id] = b[id << 1] + b[id << 1 | 1];
}
void update(int pos, int val) {
update(1, 1, n, pos, val);
}
int get(int id, int l, int r, int u, int v) {
if (l > v || u > r) {
return 0;
}
if (u <= l && r <= v) {
return b[id];
}
int mid = (l + r) >> 1;
return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
}
int get(int l, int r) {
return get(1, 1, n, l, r);
}
}seg;
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 = sz(x), q = sz(s);
seg.init(n);
vector < int > ans(q, 0);
REP(i, m) {
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
REP(i, q) {
ql[l[i]].push_back(i);
qr[r[i]].push_back(i);
}
dsu.init(n);
REP(i, n) {
for (auto x: g[i]) {
if (x < i) {
dsu.unite(i, x);
}
}
for (auto x: qr[i]) {
top[0][x] = dsu.find_par(e[x]);
}
}
dfs(0, n - 1, -1);
dsu.init(n);
REP(i, n) {
vector < int > ().swap(adj[i]);
}
FORD(i, n - 1, 0) {
for (auto x: g[i]) {
if (x > i) {
dsu.unite(i, x);
}
}
for (auto x: ql[i]) {
top[1][x] = dsu.find_par(s[x]);
}
}
timer = 0;
dfs(1, 0, -1);
// REP(i, n) {
// cout << i << ": " << in[0][i] << " " << in[1][i] << "\n";
// }
//
// REP(i, q) {
// cout << i << " -> " << top[0][i] << " " << top[1][i] << "\n";
// }
REP(i, q) {
int j = top[0][i];
op[in[0][j] - 1].push_back(i);
cl[out[0][j]].push_back(i);
// cout << in[0][j] - 1 << " " << out[0][j] << "\n";
}
REP(i, n) {
rev[in[0][i]] = i;
}
FOR(i, 1, n) {
int j = rev[i];
seg.update(in[1][j], 1);
for (auto x: op[i]) {
int j = top[1][x];
ans[x] -= seg.get(in[1][j], out[1][j]);
}
for (auto x: cl[i]) {
int j = top[1][x];
ans[x] += seg.get(in[1][j], out[1][j]);
}
}
REP(i, q) {
if (s[i] < l[i]) {
ans[i] = 0;
}
if (e[i] > r[i]) {
ans[i] = 0;
}
ans[i] = min(ans[i], 1);
}
return ans;
}
