#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define ld long double
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
vector<vector<int>> graph;
int smallest[3000][3000], largest[3000][3000];
int m, q;
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
m = x.size();
q = s.size();
vector<int> dum;
for (int i=0;i<n;i++) graph.pb(dum);
for (int i=0;i<m;i++) {
graph[x[i]].pb(y[i]);
graph[y[i]].pb(x[i]);
}
vector<bool> visited(n);
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) visited[j] = false;
smallest[i][i] = i;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push(mp(i, i));
while (pq.size() > 0) {
pair<int,int> node = pq.top(); pq.pop();
if (visited[node.ss]) continue;
visited[node.ss] = true;
for (int j: graph[node.ss]) {
if (!visited[j]) {
smallest[i][j] = max(node.ff, j);
pq.push(mp(smallest[i][j], j));
}
}
}
}
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) visited[j] = false;
largest[i][i] = i;
priority_queue<pair<int,int>> pq;
pq.push(mp(i, i));
while (pq.size() > 0) {
pair<int,int> node = pq.top(); pq.pop();
if (visited[node.ss]) continue;
visited[node.ss] = true;
for (int j: graph[node.ss]) {
if (!visited[j]) {
largest[i][j] = min(node.ff, j);
pq.push(mp(largest[i][j], j));
}
}
}
}
vector<int> ansvec;
for (int i=0;i<q;i++) {
bool flag = false;
for (int j=0;j<n;j++) {
if (largest[s[i]][j] >= l[i] && smallest[e[i]][j] <= r[i] && j >= l[i] && j <= r[i]) {
flag = true;
ansvec.pb(1);
break;
}
}
if (!flag) {
ansvec.pb(0);
}
}
return ansvec;
}
