#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define sp << " " <<
struct node{
int next;
int limit;
int sblen = 1;
};
vector<node> DSUhuman, DSUwarewolf;
int goDSU(int a, int limit, vector<node> &DSU){
if (DSU[a].next == a || DSU[a].limit > limit){
return a;
}
return goDSU(DSU[a].next, limit, DSU);
}
void merge(int a, int b, int limit, vector<node> &DSU){
a = goDSU(a, 1e9, DSU);
b = goDSU(b, 1e9, DSU);
if (a == b)
return;
if (DSU[a].sblen < DSU[b].sblen)
swap(a, b);
if (DSU[a].sblen == DSU[b].sblen){
DSU[b].sblen++;
}
DSU[a].limit = limit;
DSU[a].next = b;
}
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) {
int Q = S.size(), M = X.size();
std::vector<int> A(Q);
vector<vector<int>> graph(N);
DSUhuman.resize(N);
DSUwarewolf.resize(N);
for (int i = 0; i < M; i++){
graph[X[i]].push_back(Y[i]);
graph[Y[i]].push_back(X[i]);
}
for (int i = 0; i < N; i++){
DSUhuman[i].next = i;
DSUwarewolf[i].next = i;
}
for (int i = 0; i < N; i++){
for (auto go : graph[i]){
if (go < i){
merge(i, go, i, DSUwarewolf);
}
}
}
for (int i = N - 1; i >= 0; i--){
for (auto go : graph[i]){
if (go > i){
merge(i, go, N - i - 1, DSUhuman);
}
}
}
vector<array<int, 4>> road; // warewolflimit, humanlimit, source, end;
for (int i = 1; i < N - 1; i++){
int a = goDSU(i, i, DSUwarewolf), b = goDSU(i, N - 1 - i, DSUhuman), l1 = i, l2 = N - 1 - i, p = 0;
while (true){
p = b;
l2 = N - 1 - i;
while (true){
road.push_back({ l1, l2, p, a });
l2 = DSUhuman[p].limit;
if (DSUhuman[p].next == p){
break;
}
p = goDSU(p, l2, DSUhuman);
}
l1 = DSUwarewolf[a].limit;
if (DSUwarewolf[a].next == a){
break;
}
a = goDSU(a, l1, DSUwarewolf);
}
}
sort(all(road));
vector<int> out(Q);
vector<array<int, 5>> querys(Q);
for (int i = 0; i < Q; i++){
if (R[i] == N - 1 || L[i] == 0){
out[i] = 1;
}else{
querys[i][0] = R[i];
querys[i][1] = N - 1 - L[i];
querys[i][2] = goDSU(S[i], N - 1 - L[i], DSUhuman);
querys[i][3] = goDSU(E[i], R[i], DSUwarewolf);
querys[i][4] = i;
}
}
sort(all(querys));
int j = 0;
map<pair<int, int>, int> mp;
for (int i = 0; i < querys.size(); i++){
while (j < road.size() && road[j][0] <= querys[i][0]){
if (mp[{ road[j][2], road[j][3] }]){
mp[{ road[j][2], road[j][3] }] = min(road[j][1], mp[{ road[j][2], road[j][3] }]);
}else{
mp[{ road[j][2], road[j][3] }] = road[j][1];
}
j++;
}
if (mp[{ querys[i][2], querys[i][3] }] && mp[{ querys[i][2], querys[i][3] }] <= querys[i][1]){
out[querys[i][4]] = 1;
}
}
return out;
}
