#include <bits/stdc++.h>
#include "werewolf.h"
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef vector <int> vi;
const int N = 2e5 + 7;
struct T {
int n, tim;
vector <vector <int> > adj;
vector <int> par, st, en, wh;
vector <int> pa[20];
void init(int n_) {
n = n_; tim = 0;
par.clear();
st.resize(n); en.resize(n); adj.resize(n); wh.resize(n);
for (int i = 0; i < n; i++) par.pb(i);
for (int i = 0; i < 20; i++) pa[i].resize(n);
}
int find(int x) {return (par[x] == x) ? x : (par[x] = find(par[x]));}
void unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return;
par[y] = x;
adj[x].pb(y);
}
void dfs(int x, int p = -1) {
pa[0][x] = p;
wh[tim] = x;
st[x] = tim++;
for (int y : adj[x]) dfs(y, x);
en[x] = tim-1;
}
void fin() {
for (int i = 1; i < 20; i++) {
for (int j = 0; j < n; j++) {
if (pa[i-1][j] != -1) pa[i][j] = pa[i-1][pa[i-1][j]];
else pa[i][j] = -1;
}
}
}
} tl, tr;
struct qu {
int l, r, ix, o;
};
vector <qu> qe[N];
int fen[N];
void add(int x, int y) {for (x++; x < N; x += x & -x) fen[x] += y;}
int get(int x) {int out = 0; for (x++; x; x -= x & -x) out += fen[x]; return out;}
vi check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R) {
int m = X.size(), q = S.size();
tl.init(n); tr.init(n);
vector <vector <int> > adj(n);
for (int i = 0; i < m; i++) {
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
for (int i = n-1; i >= 0; i--) for (auto x : adj[i]) if (x > i) tl.unite(i, x);
for (int i = 0; i < n; i++) for (auto x : adj[i]) if (x < i) tr.unite(i, x);
tl.dfs(0);
tl.fin();
tr.dfs(n-1);
tr.fin();
for (int i = 0; i < q; i++) {
int x = S[i];
for (int j = 19; j >= 0; j--) if (tl.pa[j][x] != -1 && tl.pa[j][x] >= L[i]) x = tl.pa[j][x];
int a = tl.st[x], b = tl.en[x];
x = E[i];
for (int j = 19; j >= 0; j--) if (tr.pa[j][x] != -1 && tr.pa[j][x] <= R[i]) x = tr.pa[j][x];
int c = tr.st[x], d = tr.en[x];
if (a) qe[a-1].pb({c, d, i, -1});
qe[b].pb({c, d, i, 1});
}
vector <int> a(n), res(q, 0);
for (int i = 0; i < n; i++) a[i] = tr.st[tl.wh[i]];
for (int i = 0; i < n; i++) {
add(a[i], 1);
for (auto x : qe[i]) res[x.ix] += (get(x.r)-get(x.l-1))*x.o;
}
for (int i = 0; i < q; i++) if (res[i]) res[i] = 1;
return res;
}
