#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
using VI = vector<int>;
const int maxn = 4e5 + 5;
int N, M, Q;
int U[maxn], V[maxn];
namespace pre {
int parent[maxn];
vector<int> g[maxn], w[maxn];
int sz[maxn], par[maxn], pw[maxn];
int in[maxn], tour[maxn];
int tym = 0;
void init() {
for(int i = 0; i < N; i++) {
sz[i] = 1, par[i] = i;
}
}
int find(int u) {
return par[u] == u ? u : find(par[u]);
}
void join(int u, int v) {
int weight = max(u, v);
u = find(u), v = find(v);
if(u == v) return;
if(sz[u] > sz[v]) swap(u, v);
par[u] = v, pw[u] = weight;
sz[v] += sz[u];
g[v].emplace_back(u);
w[v].emplace_back(weight);
}
void dfs(int u) {
tour[tym] = u;
in[u] = tym++;
for(int v : g[u]) {
dfs(v);
}
}
pair<int, int> range(int u, int weight) {
while(par[u] != u and pw[u] <= weight)
u = par[u];
if(sz[u] == 1) // leaf
return {in[u], in[u]};
int it = upper_bound(all(w[u]), weight) - w[u].begin();
if(it == 0) // can't go nowhere
return {in[u], in[u]};
int v = g[u][it - 1];
return {in[u], in[v] + sz[v] - 1};
}
vector<int> reachable_nodes(int u, int weight) {
int l, r;
tie(l, r) = range(u, weight);
return vector<int>(tour + l, tour + r + 1);
}
}
namespace suf {
int parent[maxn];
vector<int> g[maxn], w[maxn];
int sz[maxn], par[maxn], pw[maxn];
int in[maxn], tour[maxn];
int tym = 0;
void init() {
for(int i = 0; i < N; i++) {
sz[i] = 1, par[i] = i;
}
}
int find(int u) {
return par[u] == u ? u : find(par[u]);
}
void join(int u, int v) {
int weight = min(u, v);
u = find(u), v = find(v);
if(u == v) return;
if(sz[u] > sz[v]) swap(u, v);
par[u] = v, pw[u] = weight;
sz[v] += sz[u];
g[v].emplace_back(u);
w[v].emplace_back(weight);
}
void dfs(int u) {
tour[tym] = u;
in[u] = tym++;
for(int v : g[u]) {
dfs(v);
}
}
pair<int, int> range(int u, int weight) {
while(par[u] != u and pw[u] >= weight)
u = par[u];
if(sz[u] == 1) // leaf
return {in[u], in[u]};
int it = upper_bound(all(w[u]), weight, [](int x, int y){ return x > y; }) - w[u].begin();
if(it == 0) // can't go nowhere
return {in[u], in[u]};
int v = g[u][it - 1];
return {in[u], in[v] + sz[v] - 1};
}
vector<int> reachable_nodes(int u, int weight) {
int l, r;
tie(l, r) = range(u, weight);
return vector<int>(tour + l, tour + r + 1);
}
}
vector<int> check_validity(int _N, VI X, VI Y, VI S, VI E, VI L, VI R) {
N = _N, M = X.size(), Q = S.size();
for(int i = 0; i < M; i++) {
U[i] = X[i], V[i] = Y[i];
if(U[i] > V[i]) swap(U[i], V[i]);
}
pre::init();
suf::init();
vector<int> p(M), q(M);
iota(p.begin(), p.end(), 0);
iota(q.begin(), q.end(), 0);
sort(p.begin(), p.end(), [](int x, int y){ return V[x] < V[y]; });
sort(q.begin(), q.end(), [](int x, int y){ return U[x] > U[y]; });
for(int i : p)
pre::join(U[i], V[i]);
for(int i : q)
suf::join(U[i], V[i]);
pre::dfs(pre::find(0));
suf::dfs(suf::find(0));
vector<int> ans;
for(int i = 0; i < Q; i++) {
vector<int> leq = pre::reachable_nodes(E[i], R[i]);
vector<int> geq = suf::reachable_nodes(S[i], L[i]);
sort(all(leq));
sort(all(geq));
vector<int> intersection;
auto it = set_intersection(all(leq), all(geq), back_inserter(intersection));
ans.emplace_back(bool(intersection.size()));
}
return ans;
}
