#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <ll, ll>;
using vii = vector <ii>;
const ll MAXN = 2E5+16;
struct Edge {
ll u, v, w;
};
struct DSU {
vll par, sz, nn, bioPar;
ll n;
// vector <vii> qs;
// vll vans;
vii funnyEgs;
vector <vll> adj;
function <ll(ll, ll)> a;
ll newId () {
ll id = par.size();
par.push_back(id);
bioPar.push_back(id);
sz.push_back(1);
adj.push_back(vll({}));
nn.push_back(-15);
return id;
}
DSU (ll n, function <ll(ll, ll)> a): par(n), sz(n, 1), nn(n), bioPar(n), /* qs(n, vii({})), */ funnyEgs(0), adj(n, vll({})), a(a), n(n) { iota(par.begin(), par.end(), 0); iota(nn.begin(), nn.end(), 0); }
ll find (ll u) { return u == par[u] ? u : par[u] = find(par[u]); }
void join (ll u, ll v) {
// cerr << "at-1\n";
u = find(u);
v = find(v);
if (u == v) return;
// cerr << "at0\n";
ll id = newId();
// cerr << "at1\n";
adj[id].push_back(u);
adj[id].push_back(v);
// cerr << "at2\n";
bioPar[id] = id;
// cerr << "at3\n";
bioPar[u] = par[u] = id;
bioPar[v] = par[v] = id;
// cerr << "at4\n";
nn[id] = a(nn[u], nn[v]);
// cerr << id << " par of " << u << ' ' << v << '\n';
// cerr << "at5\n";
// if (qs[u].size() > qs[v].size()) swap(u, v);
// for (auto [vth, qid] : qs[u]) {
// if (find(vth) == v) {
// vans[qid] = id;
// } else qs[v].push_back({ vth, qid });
// }
}
ll findRoot (ll u, ll x) {
if (bioPar[u] == u) return u;
if (a(nn[bioPar[u]], x) == x) return findRoot(bioPar[u], x);
return u;
}
vll doDfs (ll u, ll x) {
ll ahm = findRoot(u, x);
vll ans;
dfs(ahm, ans);
return ans;
}
void dfs (ll u, vll &sub) {
// cerr << nn[u] << ' ';
assert(adj[u].empty() == (u < n));
if (adj[u].empty()) sub.push_back(u);
for (ll v : adj[u]) {
dfs(v, sub);
// cerr << nn[u] << ' ';
}
}
// void addQ (ll u, ll v, ll qid) {
// assert(qid == vans.size());
// qs[u].push_back({ v, qid });
// qs[v].push_back({ u, qid });
// vans.push_back(-15);
// }
};
vi check_validity (int n, vi us, vi vs, vi s, vi e, vi vl, vi vr) {
ll Q = s.size();
vector <Edge> egsMn, egsMx;
for (ll i = 0; i < us.size(); i++) {
// adj[us[i]].push_back(vs[i]);
// adj[vs[i]].push_back(us[i]);
egsMn.push_back({ us[i], vs[i], min(us[i], vs[i]) });
egsMx.push_back({ us[i], vs[i], max(us[i], vs[i]) });
}
sort(egsMn.begin(), egsMn.end(), [&](Edge a, Edge b) { return a.w > b.w; });
sort(egsMx.begin(), egsMx.end(), [&](Edge a, Edge b) { return a.w < b.w; });
DSU dsuMn(n, [&](ll a, ll b) { return min(a, b); });
for (auto [u, v, w] : egsMn) {
// cerr << u << ' ' << v << ' ' << w << '\n';
// cerr << "joining\n";
dsuMn.join(u, v);
// cerr << "joiningee\n";
}
DSU dsuMx(n, [&](ll a, ll b) { return max(a, b); });
for (auto [u, v, w] : egsMx) {
// cerr << u << ' ' << v << ' ' << w << '\n';
// cerr << "joining\n";
dsuMx.join(u, v);
// cerr << "joiningee\n";
}
vll eee;
dsuMn.dfs(dsuMn.par.size()-1, eee);
// cerr << << '\n';
vi ans(Q, -15);
for (ll qid = 0; qid < Q; qid++) {
assert(vl[qid] <= s[qid]);
assert(e[qid] <= vr[qid]);
assert(vl[qid] <= vr[qid]);
assert(e[qid] != s[qid]);
// ll ancMn = dsuMn.findRoot(s[qid], vl[qid]);
// ll ancMx = dsuMx.findRoot(e[qid], vr[qid]);
vll accMn = dsuMn.doDfs(s[qid], vl[qid]);
vll accMx = dsuMx.doDfs(e[qid], vr[qid]);
sort(accMn.begin(), accMn.end());
ans[qid] = 0;
for (ll i : accMx) {
ans[qid] |= binary_search(accMn.begin(), accMn.end(), i);
}
// for (ll i : accMn) cerr << i << ' '; cerr << '\n';
// for (ll i : accMx) cerr << i << ' '; cerr << '\n';
}
// cerr << "ANS DONE\n";
return ans;
}
