//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "werewolf.h"
#define vi vector<int>
#define pb push_back
using namespace std;
const int MAXN = 2e5 + 50;
vi adj[MAXN], ltree[MAXN], rtree[MAXN], lArr[MAXN], rArr[MAXN];
int par[MAXN], sz[MAXN], lA[MAXN], rA[MAXN], ind[MAXN];
int stL[MAXN], enL[MAXN], stR[MAXN], enR[MAXN];
int lPar[18][MAXN], rPar[18][MAXN];
set<int> comp[MAXN];
int n, m, q, t, BIT[MAXN], tmp[2*MAXN];
void add(int ind, int v) {
ind++;
while (ind < MAXN) {
BIT[ind] += v;
ind += ind & -ind;
}
}
int sum(int ind) {
ind++;
int ret = 0;
while (ind > 0) {
ret += BIT[ind];
ind -= ind & -ind;
}
return ret;
}
void ldfs(int u, int p) {
stL[u] = t;
lA[t++] = u;
for (int v: ltree[u])
if (v != p) {
ldfs(v, u);
lPar[0][v] = u;
}
enL[u] = t - 1;
}
void rdfs(int u, int p) {
stR[u] = t;
rA[t++] = u;
for (int v: rtree[u])
if (v != p) {
rdfs(v, u);
rPar[0][v] = u;
}
enR[u] = t - 1;
}
int qry(int x) {
return x == par[x] ? x : par[x] = qry(par[x]);
}
void join(int x, int y) {
x = qry(x), y = qry(y);
if (x == y) return;
if (sz[x] > sz[y]) swap(x, y);
par[x] = y;
sz[y] += sz[x];
comp[y].insert(comp[x].begin(), comp[x].end());
comp[x].clear();
}
void init() {
for (int i = 0; i < n; i++) {
par[i] = i;
sz[i] = 1;
comp[i] = {i};
}
}
vi check_validity(int N, vi x, vi y, vi s, vi e, vi l, vi r) {
n = N, m = x.size(), q = l.size();
for (int i = 0; i < m; i++) {
adj[x[i]].pb(y[i]);
adj[y[i]].pb(x[i]);
}
init();
for (int i = 0; i < n; i++) { // r
for (int v: adj[i]) {
if (v > i || qry(i) == qry(v)) continue;
int u = *(--comp[qry(v)].end());
join(i, u);
rtree[i].pb(u);
rtree[u].pb(i);
}
}
init();
for (int i = n - 1; i >= 0; i--) { // l
for (int v: adj[i]) {
if (v < i || qry(i) == qry(v)) continue;
int u = *(comp[qry(v)].begin());
join(i, u);
ltree[i].pb(u);
ltree[u].pb(i);
}
}
for (int i = 0; i < 18; i++)
fill(lPar[i], lPar[i] + MAXN, 0), fill(rPar[i], rPar[i] + MAXN, n - 1);
t = 0;
ldfs(0, -1);
t = 0;
rdfs(n - 1, -1);
for (int i = 1; i < 18; i++)
for (int j = 0; j < n; j++)
lPar[i][j] = lPar[i - 1][lPar[i - 1][j]],
rPar[i][j] = rPar[i - 1][rPar[i - 1][j]];
for (int i = 0; i < n; i++)
ind[rA[i]] = i;
vi ret;
for (int i = 0; i < q; i++) {
ret.pb(0);
int u = s[i];
for (int j = 17; j >= 0; j--)
if (lPar[j][u] >= l[i])
u = lPar[j][u];
lArr[stL[u]].pb(i);
rArr[enL[u]].pb(i);
}
for (int i = 0; i < n; i++) {
for (int j: lArr[i]) {
int u = e[j];
for (int k = 17; k >= 0; k--)
if (rPar[k][u] <= r[j])
u = rPar[k][u];
tmp[j] = sum(enR[u]) - sum(stR[u] - 1);
}
add(ind[lA[i]], 1);
for (int j: rArr[i]) {
int u = e[j];
for (int k = 17; k >= 0; k--)
if (rPar[k][u] <= r[j])
u = rPar[k][u];
if (sum(enR[u]) - sum(stR[u] - 1) != tmp[j])
ret[j] = 1;
else
ret[j] = 0;
}
}
return ret;
}
