#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
int N, M, Q;
vector<int> ans;
vector<int> adj[202020];
vector<int> tre[404040];
vector<int> qv[202020];
int st[20][404040];
int mx[20][404040];
int lft[404040];
int rgt[404040];
int pos[202020];
int id;
struct DSU {
set<int> V[202020];
int sz[404040];
int p[404040];
void init(int n, bool isV) {
for(int i = 0; i < n; i++) {
p[i] = i;
if(isV) {
sz[i] = 1;
V[i].insert(pos[i]);
}
}
}
int par(int x) {
if(x == p[x]) return x;
return p[x] = par(p[x]);
}
bool unite(int a, int b, bool isV) {
a = par(a); b = par(b);
if(a == b) return false;
if(isV) {
if(sz[a] < sz[b]) return unite(b, a, isV);
sz[a] += sz[b];
if(isV) for(int i : V[b]) V[a].insert(i);
p[b] = a;
}
else p[b] = a;
return true;
}
}uf;
void dfs(int v, int p) {
st[0][v] = p;
mx[0][v] = max(v, p);
if(!p) mx[0][v] = 1010101010;
if(v < N) {
lft[v] = rgt[v] = id;
pos[v] = id;
id++;
return;
}
lft[v] = 2 * N; rgt[v] = -1;
for(int i : tre[v]) {
if(i == p) continue;
dfs(i, v);
lft[v] = min(lft[v], lft[i]);
rgt[v] = max(rgt[v], rgt[i]);
}
}
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) {
::N = N;
M = X.size();
Q = S.size();
ans.resize(Q);
for(int i = 0; i < M; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
uf.init(2 * N, false);
for(int i = 0; i < N; i++) {
tre[N + i].push_back(i);
uf.unite(N + i, i, false);
for(int j : adj[i]) {
if(j > i) continue;
int tmp = uf.par(j);
if(uf.unite(i, j, false)) tre[N + i].push_back(tmp);
}
}
// for(int i = 0; i < 2 * N; i++) {
// printf("%d: ", i);
// for(int j : tre[i]) printf("%d ", j); puts("");
// }
dfs(2 * N - 1, 0);
for(int i = 1; i <= 19; i++) {
for(int j = 0; j < 2 * N; j++) {
st[i][j] = st[i - 1][st[i - 1][j]];
mx[i][j] = max(mx[i - 1][j], mx[i - 1][st[i - 1][j]]);
}
}
// for(int i = 0; i < N; i++) printf("%d ", pos[i]); puts("");
for(int i = 0; i < Q; i++) {
qv[L[i]].push_back(i);
}
uf.init(N, true);
for(int i = N - 1; i >= 0; i--) {
for(int j : adj[i]) {
if(j < i) continue;
uf.unite(i, j, true);
}
for(int j : qv[i]) {
int u = E[j];
for(int k = 19; k >= 0; k--) {
if(mx[k][u] > N + R[j]) continue;
u = st[k][u];
}
// lft[u], rgt[u];
int s = uf.par(S[j]);
auto it = uf.V[s].lower_bound(lft[u]);
if(it != uf.V[s].end() && *it <= rgt[u]) ans[j] = 1;
}
}
return ans;
}
