#include "werewolf.h"
#include<iostream>
#include<queue>
#include<unordered_set>
#include<algorithm>
#include<iomanip>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define us unordered_set<int>
#define vp vector<pi>
#define vvp vector<vp>
vvi Adj;
void us_print(us& L1) {
cerr << "{";
for (auto i : L1) {
cerr << i << ", ";
}
cerr << "}";
}
struct treeNode {
int v = -1;
int par = -1;
us US;
void print() {
cerr << "treeNode : {";
cerr << "v : " << v << ", ";
cerr << "par : " << par << ", ";
cerr << "US : ";
us_print(US);
cerr << "}" << endl;
}
void merge(us US2) {
if (US2.size() > US.size()) swap(US2, US);
for (auto i : US2) {
US.insert(i);
}
}
};
vector<treeNode> TN1, TN2;
int find(int a, vector<treeNode> &TN){
//cerr << "find " << a << endl;
return TN[a].par == -1 ? a : TN[a].par = find(TN[a].par, TN);
}
void print(vector<treeNode>& L1) {
for (auto i : L1) {
i.print();
}
}
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 Q = S.size();
vi A(Q, -1);
Adj = vvi(N);
TN1 = vector<treeNode>(N);
TN2 = vector<treeNode>(N);
for (int i = 0; i < X.size(); i++) {
Adj[X[i]].push_back(Y[i]);
Adj[Y[i]].push_back(X[i]);
}
vp LS(Q), RS(Q);
for (int i = 0; i < Q; i++) {
LS[i] = {L[i], i};
RS[i] = {R[i], i};
}
sort(LS.begin(), LS.end());
sort(RS.begin(), RS.end());
int rsp = 0;
for (int i = 0; i < N; i++) {
//cerr << i << endl;
TN1[i].v = i;
for (auto j : Adj[i]) {
if (j > i) continue;
if (find(j, TN1) != i) {
TN1[find(j, TN1)].par = i;
}
}
while (rsp < Q && RS[rsp].first <= i) {
//cerr << "rsp : " << rsp << endl;
int a = RS[rsp].second;
//cerr << "a : " << a << endl;
TN1[find(E[a], TN1)].US.insert(a);
rsp++;
}
}
//print(TN1);
int lsp = Q-1;
for (int i = N-1; i > -1; i--) {
//cerr << "i : " << i << endl;
TN2[i].v = i;
TN2[i].US = TN1[i].US;
for (auto j : Adj[i]) {
//cerr << "j " << j << endl;
if (j < i) continue;
if (find(j, TN2) != i) {
TN2[i].merge(TN2[find(j, TN2)].US);
TN2[find(j, TN2)].par = i;
}
}
//cerr << "oink" << endl;
while (lsp > -1 && LS[lsp].first >= i) {
int a = LS[lsp].second;
int c = S[a];
lsp--;
//cerr << "a : " << a << endl;
//cerr << "find(c) : " << find(c, TN2) << endl;
treeNode& b = TN2[find(c, TN2)];
//b.print();
A[a] = (b.US.find(a) != b.US.end());
//print(TN2);
}
}
//print(TN2);
return A;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
