#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1,(n))
#define f first
#define s second
#define pb push_back
typedef vector<int> vi;
typedef pair<int, int> pii;
const int MAXN = 200100;
int par[2*MAXN];
int find (int a) {return par[a] = par[a]==a ? a : find(par[a]);}
bool same (int a, int b) {return find(a) == find(b);}
void unite (int a, int b) {
a = find(a), b = find(b);
if (a == b) return;
par[b] = a;
}
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();
int m = (int)X.size();
std::vector<int> A(Q);
for (int i = 0; i < Q; ++i) {
FOR(j, 0, n-1) FOR(k, 0, 1) par[k*n + j] = k*n + j;
FOR(j, L[i], R[i]) unite(j, n+j);
//FOR(j, L[i], R[i]) cout <<" uniting " << j << ", " << n+j << endl;
FOR(j, 0, m-1) {
int u = X[j], v = Y[j];
if (u > v) swap(u, v);
if (u >= L[i]) unite(u, v);
// if (u >= L[i]) cout << " uniting " << u << ", " << v << endl;
if (v <= R[i]) unite(n+u,n+v);
// if (v <= R[i]) cout << " uniting " << n+u << ", " << n+v << endl;
}
A[i] = same(S[i], n+E[i]);
//cout << " ans: " << A[i] << endl;
}
return A;
}
