#include <bits/stdc++.h>
#include "werewolf.h"
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
void DfsMax(vvi &graph, int node, int max, vb &visited) {
visited[node] = true;
for (int neighbor : graph[node]) {
if (neighbor <= max && !visited[neighbor]) DfsMax(graph, neighbor, max, visited);
}
}
void DfsMin(vvi &graph, int node, int min, vb &visited) {
visited[node] = true;
for (int neighbor : graph[node]) {
if (neighbor >= min && !visited[neighbor]) DfsMin(graph, neighbor, min, visited);
}
}
vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {
int m = x.size();
vvi graph(n);
for (int i = 0; i < m; i++) {
graph[x[i]].push_back(y[i]);
graph[y[i]].push_back(x[i]);
}
int q = s.size();
vi ans(q);
for (int i = 0; i < q; i++) {
vb visited1(n), visited2(n);
DfsMin(graph, s[i], l[i], visited1);
DfsMax(graph, e[i], r[i], visited2);
for (int j = 0; j < n; j++) {
if (visited1[j] && visited2[j]) {
ans[i] = 1;
break;
}
}
}
return ans;
}
//6 6 3
//0 3
//1 2
//1 5
//1 3
//2 5
//3 4
//
//4 2 1 2
//4 2 2 2
//5 4 3 4
