#include "werewolf.h"
#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
// const int B = 640;
const int N = 4e5 + 5;
int f[N], sz[N];
int father(int x) {
if (f[x] != f[f[x]])
return f[x] = father(f[x]);
return f[x];
}
void join(int u, int v) {
int su = u, sv = v;
u = father(u), v = father(v);
if (u == v)
return;
// cout << "joining ";
// cout << su << ' ' << sv << '\n';
if (sz[u] < sz[v])
swap(u, v);
sz[u] += sz[v];
f[v] = u;
}
int same(int u, int v) {
return father(u) == father(v);
}
// vector <int> g[N];
// int vis[N], mask[N];
vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
// for (int i = 0; i < N; i++)
// vis[i] = -1, mask[i] = 0;
int q = S.size(), m = X.size();
vector<int> A(q, 0);
// vector <ar <int, 2>> LP(m), RP(m);
// for (int i = 0; i < m; i++) {
// if (X[i] > Y[i])
// swap(X[i], Y[i]);
// LP[i] = {X[i], Y[i]};
// RP[i] = {Y[i] + n, X[i] + n};
// }
// sort(all(LP));
// sort(all(RP));
// vector <ar <int, 3>> qrs[m / B + 10];
for (int id = 0; id < q; id++) {
// if (L[id] == 1 || R[id] == n - 1) {
// A[id] = 1;
// continue;
// }
// cout << "\n\nseeing query " << id << '\n';
for (int i = 0; i < 2 * n; i++)
f[i] = i, sz[i] = 1;
for (int i = 0; i < n; i++)
join(i, i + n);
for (int i = 0; i < m; i++) {
if (L[id] <= min(X[i], Y[i])) {
join(Y[i], X[i]);
}
if (max(X[i], Y[i]) <= R[id]) {
join(X[i] + n, Y[i] + n);
}
}
A[id] = same(S[id], E[id] + n);
}
// for (int curB = 0; curB * B < m; curB++) { // current block
// // cout << "\n\n\nupdate\n";
// for (int i = 0; i < 2 * n; i++)
// f[i] = i, sz[i] = 1;
// for (int i = 0; i < n; i++)
// join(i, i + n);
// int nxt = (curB + 1) * B;
// for (int t = nxt; t < m; t++)
// join(LP[t][0], LP[t][1]);
// sort(all(qrs[curB]));
// int t = -1;
// for (auto &[r, l, i] : qrs[curB]) {
// // cout << "seeing query " << i << '\n';
// while (t + 1 <= r)
// t++, join(RP[t][0], RP[t][1]);
// A[i] = same(S[i], E[i]);
// if (A[i])
// continue;
// stack <int> q;
// for (int j = l; j < nxt && j < m; j++) {
// int u = LP[j][0], v = LP[j][1];
// g[u].emplace_back(v);
// g[v].emplace_back(u);
// q.push(u);
// }
// while (!q.empty()) {
// int x = q.top(); q.pop();
// if (vis[x] == -1)
// vis[x] = x;
// mask[vis[x]] |= same(x, S[i]) * 1;
// mask[vis[x]] |= same(x, E[i]) * 2;
// // cout << x << ' ' << vis[x] << ' ' << mask[vis[x]] << '\n';
// if (mask[vis[x]] == 3) {
// A[i] = 1;
// break;
// }
// for (int y : g[x]) {
// // cout << "edge ";
// // cout << x << ' ' << y << '\n';
// if (vis[y] == -1) {
// vis[y] = vis[x];
// q.push(y);
// }
// }
// }
// for (int j = l; j < nxt && j < m; j++) {
// int u = LP[j][0], v = LP[j][1];
// g[u].clear(), g[v].clear();
// vis[u] = vis[v] = -1, mask[u] = mask[v] = 0;
// }
// }
// }
return A;
}
