#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define MP make_pair
typedef vector<int> vi;
typedef pair<int, int> pii;
const int mxn = 4e5 + 10;
int n, m, q, cnt, timer;
int par[mxn], query[mxn];
vi ord, chi[mxn];
set<int> STL[mxn];
void clear() {
cnt = n;
timer = 0;
memset(par, -1, sizeof par);
}
int parent(int u) {
return par[u] < 0 ? u : par[u] = parent(par[u]);
}
int unite(int u, int v, bool sus = false) {
u = parent(u);
v = parent(v);
if(u == v) return -1;
if(sus) {
if(STL[u].size() < STL[v].size())
swap(STL[u], STL[v]);
swap(STL[cnt], STL[u]);
for(int x : STL[v])
STL[cnt].insert(x);
STL[v].clear();
}
par[u] = cnt;
par[v] = cnt;
chi[cnt].push_back(u);
chi[cnt].push_back(v);
return (cnt++);
}
pii pos[mxn];
void dfs(int u) {
pos[u].ff = timer;
if(u < n) {
ord.push_back(u);
timer++;
pos[u].ss = timer;
return;
}
for(int v : chi[u])
dfs(v);
pos[u].ss = timer;
}
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
#ifdef LOCAL
cout << "This is LOCAL\n";
#endif
n = N;
m = X.size();
q = S.size();
vector<pii> HQ[n];
vector<pii> WQ[n];
for(int i = 0; i < m; i++) {
int mn = min(X[i], Y[i]);
int mx = max(X[i], Y[i]);
HQ[mn].push_back(MP(-1, mx));
WQ[mx].push_back(MP(-1, mn));
}
for(int i = 0; i < q; i++) {
int l = L[i], r = R[i];
HQ[l].push_back(MP(i, S[i]));
WQ[r].push_back(MP(i, E[i]));
}
#ifdef LOCAL
cout << "\nHumans\n";
#endif
clear();
for(int u = n - 1; u >= 0; u--) {
for(pii p : HQ[u]) {
int i = p.ff;
int v = p.ss;
if(i == -1) {
int a = unite(u, v);
#ifdef LOCAL
cout << "unite 0: " << u << ' ' << v << " --> " << a << endl;
#endif
}
else {
int a = parent(v);
query[i] = a;
#ifdef LOCAL
cout << " * query " << i << ": " << v << " -> (" << u << ", " << n - 1 << ") = " << a << endl;
#endif
}
}
}
bool vis[2 * n];
memset(vis, 0, sizeof vis);
for(int i = 0; i < n; i++) {
int a = parent(i);
if(vis[a] == 0) {
dfs(a);
vis[a] = 1;
}
}
// dfs(cnt - 1);
#ifdef LOCAL
for(int x : ord)
cout << x << ' ';
cout << endl;
for(int i = 0; i < cnt; i++) {
cout << i << ": " << pos[i].ff << ' ' << pos[i].ss << endl;
}
#endif
clear();
for(int i = 0; i < n; i++)
STL[i].insert(pos[i].ff);
#ifdef LOCAL
cout << "\nWolves\n";
#endif
vi ret(q);
for(int u = 0; u < n; u++) {
for(pii p : WQ[u]) {
int i = p.ff;
int v = p.ss;
if(i == -1) {
int a = unite(u, v, 1);
#ifdef LOCAL
cout << "unite 1: " << u << ' ' << v << " --> " << a << endl;
#endif
}
else {
int a = parent(v);
int A = query[i];
auto it = STL[a].lower_bound(pos[A].ff);
if(it != STL[a].end() && (*it) < pos[A].ss)
ret[i] = 1;
else
ret[i] = 0;
#ifdef LOCAL
cout << " * ans " << i << " = " << v << " -> (0, " << u << ") = " << ret[i] << endl;
#endif
// cout << a << ": ";
// for(int x : STL[a]) {
// cout << x << ' ';
// }
// cout << endl;
// cout << A << ": ";
// for(int i = pos[A].ff; i < pos[A].ss; i++) {
// cout << ord[i] << ' ';
// }
// cout << endl;
}
}
}
return ret;
}
/*
10 9 10
6 7
1 5
8 0
2 9
9 4
2 7
8 5
6 0
3 4
4 9 0 9
8 1 8 9
1 8 1 8
8 3 5 5
8 9 3 9
0 1 0 2
9 0 6 6
1 7 1 8
9 4 5 6
9 5 0 9
*/
