#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
int cm, cnt;
vector<int> vs, ve, sl, sr, el, er, pp, pm, pl, pr;
vector<vector<int>> g;
int find(int a){
if (a == pp[a]) return pp[a];
return pp[a] = find(pp[a]);
}
void merge(int a, int b, bool sht=false){
//cout << a << " " << b << endl;
a = find(a);
b = find(b);
if (a == b) return;
pp[b] = a;
pl[a] = min(pl[a], pl[b]);
pr[a] = max(pr[a], pr[b]);
if (sht) return;
if (pm[a] == -1) g[cm].push_back(-a-1);
else g[cm].push_back(pm[a]);
if (pm[b] == -1) g[cm].push_back(-b-1);
else g[cm].push_back(pm[b]);
pm[a] = cm;
cm++;
}
void dfs(int cur, vector<int>& v){
if (cur < 0){
v[-cur-1] = cnt;
cnt++;
return;
}
for (int next : g[cur]) dfs(next, v);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
int M = X.size();
int Q = S.size();
vector<pair<int,pair<int,int>>> es, ee;
for (int i=0; i<M; i++){
es.push_back({min(X[i], Y[i]), {X[i], Y[i]}});
ee.push_back({max(X[i], Y[i]), {X[i], Y[i]}});
}
vector<pair<int,pair<int,int>>> qs, qe;
for (int i=0; i<Q; i++){
qs.push_back({L[i], {S[i], i}});
qe.push_back({R[i], {E[i], i}});
}
//cout << "a" << endl;
sort(es.begin(), es.end());
sort(ee.begin(), ee.end());
sort(qs.begin(), qs.end());
sort(qe.begin(), qe.end());
vs.resize(N);
ve.resize(N);
sl.resize(Q);
sr.resize(Q);
el.resize(Q);
er.resize(Q);
pp.resize(N);
pm.resize(N);
pl.resize(N);
pr.resize(N);
//cout << "b" << endl;
for (int i=0; i<N; i++){
pp[i] = i;
pm[i] = -1;
}
g.assign(N-1, vector<int>(0));
cm = 0;
for (int i=M-1; i>=0; i--) merge(es[i].second.first, es[i].second.second);
//cout << "c" << endl;
cnt = 0;
dfs(N-2, vs);
//cout << "d" << endl;
for (int i=0; i<N; i++){
pp[i] = i;
pl[i] = vs[i];
pr[i] = vs[i];
}
//for (int i=0; i<N; i++) cout << vs[i] << " ";
//cout << endl;
//cout << "e" << endl;
int cur = Q-1;
for (int i=M-1; i>=0; i--){
//cout << i << endl;
while (cur >= 0 && es[i].first < qs[cur].first){
//cout << cur << endl;
sl[qs[cur].second.second] = pl[find(qs[cur].second.first)];
sr[qs[cur].second.second] = pr[find(qs[cur].second.first)];
cur--;
}
//cout << "!" << endl;
merge(es[i].second.first, es[i].second.second, true);
//cout << "?" << endl;
}
//cout << "f" << endl;
while (cur >= 0){
sl[qs[cur].second.second] = pl[find(qs[cur].second.first)];
sr[qs[cur].second.second] = pr[find(qs[cur].second.first)];
cur--;
}
for (int i=0; i<N; i++){
pp[i] = i;
pm[i] = -1;
}
g.assign(N-1, vector<int>(0));
cm = 0;
for (int i=0; i<M; i++) merge(ee[i].second.first, ee[i].second.second);
cnt = 0;
dfs(N-2, ve);
for (int i=0; i<N; i++){
pp[i] = i;
pl[i] = ve[i];
pr[i] = ve[i];
}
cur = 0;
for (int i=0; i<M; i++){
while (cur < Q && ee[i].first > qe[cur].first){
el[qe[cur].second.second] = pl[find(qe[cur].second.first)];
er[qe[cur].second.second] = pr[find(qe[cur].second.first)];
cur++;
}
merge(ee[i].second.first, ee[i].second.second, true);
}
while (cur < Q){
el[qe[cur].second.second] = pl[find(qe[cur].second.first)];
er[qe[cur].second.second] = pr[find(qe[cur].second.first)];
cur++;
}
vector<int> A(Q);
for (int i=0; i<Q; i++){
A[i] = 0;
for (int j=0; j<N; j++){
if (sl[i] <= vs[j] && vs[j] <= sr[i] && el[i] <= ve[j] && ve[j] <= er[i]) A[i] = 1;
}
}
return A;
}
