#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[202020];
vector<int> tre[202020];
int Q, M, N;
int p[202020];
int st[20][202020];
int mn[20][202020];
int mx[20][202020];
int dep[202020];
int fd(int x) {
if(x == p[x]) return x;
return p[x] = fd(p[x]);
}
void unite(int a, int b) {
a = fd(a); b = fd(b);
if(a == b) return;
p[a] = b;
}
void dfs(int now, int par) {
dep[now] = dep[par] + 1;
st[0][now] = mx[0][now] = mn[0][now] = par;
if(!now) mn[0][now] = -1;
for(int i : tre[now]) {
if(i == par) continue;
dfs(i, now);
}
}
int lca(int a, int b) {
if(dep[a] < dep[b]) return lca(b, a);
for(int i = 19; i >= 0; i--) {
if(dep[st[i][a]] < dep[b]) continue;
a = st[i][a];
}
if(a == b) return a;
for(int i = 19; i >= 0; i--) {
if(st[i][a] == st[i][b]) continue;
a = st[i][a]; b = st[i][b];
}
return st[0][a];
}
int find_yellow(int v, int u, int x) {
if(v > x) return v;
for(int i = 19; i >= 0; i--) {
if(mx[i][v] > x) continue;
if(dep[st[i][v]] < dep[u]) continue;
v = st[i][v];
}
return v;
}
int find_blue(int v, int u, int x) {
if(v < x) return v;
for(int i = 19; i >= 0; i--) {
if(mn[i][v] < x) continue;
if(dep[st[i][v]] < dep[u]) continue;
v = st[i][v];
}
return v;
}
vector<int> ans;
void yes() { ans.push_back(1); }
void no() { ans.push_back(0); }
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) {
Q = S.size();
M = X.size();
N = _N;
for(int i = 0; i < M; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for(int i = 0; i < N; i++) sort(adj[i].begin(), adj[i].end());
for(int i = 0; i < N; i++) p[i] = i;
for(int i = N - 2; i >= 0; i--) {
for(int j : adj[i]) {
if(fd(j) == fd(i)) continue;
tre[i].push_back(j);
tre[j].push_back(i);
unite(i, j);
}
}
dfs(0, 200002);
for(int i = 1; i <= 19; i++) {
for(int j = 0; j < N; j++) {
st[i][j] = st[i - 1][st[i - 1][j]];
mn[i][j] = min(mn[i - 1][j], mn[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 < Q; i++) {
if(S[i] < L[i] || E[i] > R[i]) { no(); continue; }
int l = lca(S[i], E[i]);
int s = S[i], e = E[i];
s = find_blue(s, l, L[i]);
e = find_yellow(e, l, R[i]);
if(s == l && e == l) {
yes(); continue;
}
if(dep[s] > dep[l]) s = find_yellow(s, l, R[i]);
else e = find_blue(e, l, L[i]);
if(s == l && e == l) yes();
else no();
}
return ans;
}
