#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
using namespace std;
using VI = vector <int>;
const int N = 3e3+1;
int n, m, q;
vector <int> paths[N];
int ans[N];
struct Query {
int st, ed, l, r, id;
// l means I can use city x in human form (l <= x < n)
// r means I can use city x in wolf form (0 <= x <= r)
};
int solve(int st, int ed, int l, int r) {
// cout << st << ' ' << ed << ' ' << l << ' ' << r << '\n';
int vis[n];
memset(vis, 0, sizeof(vis));
queue <int> bfs; bfs.push(st);
queue <int> bfs1;
while(!bfs.empty()) {
int x = bfs.front(); bfs.pop();
if (x < l || vis[x]==1) continue;
vis[x] = 1; bfs1.push(x);
for (auto el : paths[x])
bfs.push(el);
}
while(!bfs1.empty()) {
int x = bfs1.front(); bfs1.pop();
if (x > r || vis[x]==2) continue;
vis[x] = 2;
for (auto el : paths[x])
bfs1.push(el);
}
return vis[ed]==2;
}
VI check_validity(int _N, VI X, VI Y, VI ST, VI ED, VI L, VI R) {
n = _N;
m = sz(X);
q = sz(ST);
for (int i = 0; i < m; i++) {
paths[X[i]].pb(Y[i]);
paths[Y[i]].pb(X[i]);
}
vector <Query> queries;
for (int i = 0; i < q; i++)
queries.pb({ST[i], ED[i], L[i], R[i], i});
VI res(q);
for (int i = 0; i < q; i++) {
// res[i] = ans[i];
res[i] = solve(queries[i].st, queries[i].ed, queries[i].l, queries[i].r);
}
return res;
}
