#include "werewolf.h"
//author: erray
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/ioi/codes/debug.h"
#else
#define debug(...) (void) 37
#endif
struct DSU {
vector<int> link;
DSU(int n) {
link.resize(n);
iota(link.begin(), link.end(), 0);
}
int get(int v) {
return link[v] = (v == link[v] ? v : get(link[v]));
}
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x == y) {
return false;
}
link[y] = x;
return true;
}
};
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 M = int(X.size());
int Q = int(E.size());
vector<vector<int>> g(N);
for (int i = 0; i < M; ++i) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
vector<int> ans(Q);
for (int q = 0; q < Q; ++q) {
DSU eg(N), sg(N);
for (int i = 0; i <= R[q]; ++i) {
for (auto u : g[i]) {
if (u < i) {
eg.unite(i, u);
}
}
}
for (int i = N - 1; i >= L[q]; --i) {
for (auto u : g[i]) {
if (u > i) {
sg.unite(i, u);
}
}
}
for (int i = 0; i < N; ++i) {
ans[q] |= (eg.get(i) == eg.get(E[q]) && sg.get(i) == sg.get(S[q]));
}
}
return ans;
}
