#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int N = 3000 + 7;
int n, m;
vector<int> le, ri;
struct dsu
{
int fat[N];
dsu()
{
iota(fat, fat + N, 0);
}
int find(int x) { return fat[x] = x == fat[x] ? x : find(fat[x]); }
void link(int u, int v)
{
u = find(u), v = find(v);
fat[u] = v;
}
inline bool same(int u, int v) { return find(u) == find(v); }
};
bool solve(int st, int en, int L, int R)
{
dsu d1, d2;
for (int i = 0; i < m; ++i)
{
int u = le[i], v = ri[i];
if (max(u, v) <= R)
d1.link(u, v);
if (min(u, v) >= L)
d2.link(u, v);
}
for (int i = L; i <= R; ++i)
{
if (d1.same(en, i) && d2.same(st, i))
return 1;
}
return 0;
}
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)
{
n = _N, m = X.size();
le = X, ri = Y;
int Q = S.size();
std::vector<int> A(Q);
for (int i = 0; i < Q; ++i)
{
A[i] = solve(S[i], E[i], L[i], R[i]);
}
return A;
}
