#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
vector<vector<int>> g, mn, mx;
vector<bool> vis;
void dfs(int u) {
vis[u] = 1;
for (auto v : g[u]) {
if (!vis[v]) {
dfs(v);
}
}
}
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();
mn.resize(n + 1, vector<int>(n + 1));
mx.resize(n + 1, vector<int>(n + 1));
auto get_max = [&](int s, int e) {
int l = 1, r = n + 1;
while (l + 1 < r) {
int k = (l + r) / 2;
g.assign(n + 1, {});
vis.assign(n + 1, 0);
for (int i = 0; i < m; i++) {
if (min(x[i], y[i]) >= k) {
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
}
dfs(s);
if (vis[e]) {
l = k;
} else {
r = k;
}
}
return l;
};
auto get_min = [&](int s, int e) {
int l = 0, r = n;
while (l + 1 < r) {
int k = (l + r) / 2;
g.assign(n + 1, {});
vis.assign(n + 1, 0);
for (int i = 0; i < m; i++) {
if (max(x[i], y[i]) <= k) {
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
}
dfs(s);
if (vis[e]) {
r = k;
} else {
l = k;
}
}
return r;
};
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
mx[i][j] = get_max(i, j);
mn[i][j] = get_min(i, j);
}
}
int q = S.size();
vector<int> ans(q);
for (int i = 0; i < q; i++) {
int s = S[i], e = E[i], l = L[i], r = R[i];
for (int j = l; j <= r; j++) {
if (mx[s][j] >= l && mn[j][e] <= r) {
ans[i] = 1;
break;
}
}
}
return ans;
}
