#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int n, m, q;
struct reachability_tree{
int n;
vector<int> p;
vector<int> w;
vector<vector<int>> v;
reachability_tree(int _n){
n = _n;
p.resize(n);
w.resize(n);
v.resize(n);
for(int i = 0; i < n; i++) p[i] = i;
}
int get(int x){
if(p[x] != x) p[x] = get(p[x]);
return p[x];
}
void unite(int a, int b, int vl){
a = get(a), b = get(b);
p[a] = n, p[b] = n;
p.pb(n);
v.pb({});
v[n].pb(a);
if(a != b) v[n].pb(b);
w.pb(vl);
n++;
}
};
vector<int> szl, szr;
vector<int> sl, sr;
void dfs(int nd, vector<int> *sz, vector<int> *s, vector<vector<int>> *v){
s->pb(nd);
for(int x: (*v)[nd]){
dfs(x, sz, s, v);
(*sz)[nd]+=(*sz)[x];
}
}
vector<int> check_validity(int n, vector<int> U, vector<int> V, vector<int> ss, vector<int> ee, vector<int> lv, vector<int> rv){
::n = n, ::m = U.size(), ::q = ss.size();
vector<pair<int, int>> edges;
for(int i = 0; i < m; i++) edges.pb({U[i], V[i]});
vector<array<int, 7>> query;
for(int i = 0; i < q; i++) query.pb({ss[i], ee[i], lv[i], rv[i], -1, -1, i});
reachability_tree rtl(n), rtr(n);
sort(edges.begin(), edges.end(), [&](pair<int, int> a, pair<int, int> b){return max(a.f, a.sc) < max(b.f, b.sc);});
sort(query.begin(), query.end(), [&](array<int, 7> a, array<int, 7> b){return a[3] < b[3];});
int cur = 0;
for(int i = 0; i < m; i++){
auto [a, b] = edges[i];
int wi = max(a, b);
rtl.unite(a, b, wi);
if(i == m-1 || wi != max(get<0>(edges[i+1]), get<1>(edges[i+1]))){
while(cur < query.size() && query[cur][3] <= wi) query[cur][4] = rtl.get(query[cur][1]), cur++;
}
}
sort(edges.begin(), edges.end(), [&](pair<int, int> a, pair<int, int> b){return min(a.f, a.sc) > min(b.f, b.sc);});
sort(query.begin(), query.end(), [&](array<int, 7> a, array<int, 7> b){return a[2] > b[2];});
cur = 0;
for(int i = 0; i < m; i++){
auto [a, b] = edges[i];
int wi = min(a, b);
rtr.unite(a, b, wi);
if(i == m-1 || wi != min(get<0>(edges[i+1]), get<1>(edges[i+1]))){
while(cur < query.size() && query[cur][2] >= wi) query[cur][5] = rtr.get(query[cur][0]), cur++;
}
}
szl.resize(rtl.n, 1);
szr.resize(rtr.n, 1);
dfs(rtl.get(0), &szl, &sl, &rtl.v);
dfs(rtr.get(0), &szr, &sr, &rtr.v);
vector<int> ans(q, 0);
vector<int> sttl(rtl.n), sttr(rtr.n);
for(int i = 0; i < rtl.n; i++) sttl[sl[i]] = i;
for(int i = 0; i < rtr.n; i++) sttr[sr[i]] = i;
for(array<int, 7> qq: query){
if(qq[0] < qq[2] || qq[1] > qq[4]) continue;
for(int i = sttl[qq[4]]; i < sttl[qq[4]] + szl[qq[4]]; i++) for(int j = sttr[qq[5]]; j < sttr[qq[5]] + szr[qq[5]]; j++) if(sl[i] == sr[j] && sl[i] < n) ans[qq[6]] = 1;
}
return ans;
}
