#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 2e5 + 20;
vector<int> adj[maxN][2];
vector<pair<int, int>> ch[maxN][2];
pair<int, int> par[maxN][2];
int depth[maxN][2];
int cnt[maxN];
int root[2];
int get_root(int u, int type) {
if (!par[u][type].second) {
return u;
}
else {
return get_root(par[u][type].second, type);
}
}
void update(int u, int v, int w, int type) {
int ru = get_root(u, type);
int rv = get_root(v, type);
if (ru == rv) {
return;
}
if (depth[ru][type] > depth[rv][type]) {
swap(ru, rv);
}
ch[rv][type].emplace_back(w, ru);
par[ru][type] = make_pair(w, rv);
if (depth[ru][type] == depth[rv][type]) {
depth[rv][type]++;
}
}
void dfs(int u, int type) {
cnt[u]++;
for (auto e: ch[u][type]) {
dfs(e.second, type);
}
}
void add(int u, int pref, int type) {
cnt[u]++;
for (int i = 0; i < pref; i++) {
dfs(ch[u][type][i].second, type);
}
}
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 M = X.size();
int Q = S.size();
for (int i = 0; i < M; i++) {
X[i]++;
Y[i]++;
if (X[i] > Y[i]) {
swap(X[i], Y[i]);
}
adj[X[i]][0].push_back(Y[i]);
adj[Y[i]][1].push_back(X[i]);
}
for (int type = 0; type < 2; type++) {
for (int u = (type ? 1 : N); (type ? u <= N : u >= 1); u += (type ? 1 : -1)) {
for (auto v: adj[u][type]) {
update(u, v, u, type);
}
}
root[type] = get_root(1, type);
}
vector<int> res(Q);
for (int i = 0; i < Q; i++) {
L[i]++;
R[i]++;
int u = S[i] + 1;
int v = E[i] + 1;
while (u != root[0] && par[u][0].first >= L[i]) {
u = par[u][0].second;
}
int pref_u = upper_bound(ch[u][0].begin(), ch[u][0].end(), make_pair(L[i], 0), greater<pair<int, int>>()) - ch[u][0].begin();
while (v != root[1] && par[v][1].first <= R[i]) {
v = par[v][1].second;
}
int pref_v = upper_bound(ch[v][1].begin(), ch[v][1].end(), make_pair(R[i], N + 1)) - ch[v][1].begin();
for (int j = 1; j <= N; j++) {
cnt[j] = 0;
}
add(u, pref_u, 0);
add(v, pref_v, 1);
for (int j = 1; j <= N; j++) {
if (cnt[j] == 2) {
res[i] = 1;
break;
}
}
}
return res;
}
