#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);
pos[u].ff = timer;
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) {
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]));
}
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 = " << a << endl;
#endif
}
}
}
dfs(cnt - 1);
#ifdef LOCAL
for(int x : ord)
cout << x << ' ';
cout << endl;
#endif
clear();
for(int i = 0; i < n; i++)
STL[i].insert(i);
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 << " = " << ret[i] << endl;
#endif
}
}
}
// cout << "n = " << n << endl;
// cout << "size = " << ret.size() << endl;
return ret;
}
