#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define srt(x) sort(all(x))
typedef long long ll;
using vi = vector<int>;
using vl = vector<ll>;
/*
N = num nodes
X, Y = edges
S, E = start and end nodes
L, R = human and werewolf cities
*/
int n, m, q;
vi x, y, s, e, l, r;
vector<vi> adj;
bool dfs(int u, int L, int R, int target, vector<bool> &seen, bool reached_transform, bool reached_vampire) {
// cout << "At node " << u << " L, R = (" << L << ", " << R << ") target = " << target << " RT? " << reached_transform << " RV? " << reached_vampire << "\n";
if (u == target) {
// cout << "Reached " << target << " did we transform? " << reached_transform << "\n";
return reached_transform;
}
bool can = false;
seen[u] = true;
for (auto v : adj[u]) {
if (seen[v]) continue;
if (reached_vampire && v > R) continue;
if (!reached_transform && v < L) continue;
bool nt = reached_transform || (v >= L && v <= R);
bool nv = reached_vampire || (v < L);
can = can || dfs(v, L, R, target, seen, nt, nv);
if (can) break;
}
seen[u] = false;
return can;
}
int answer_query(int qn) {
// cout << "answering query " << qn << "\n";
int start = s[qn], end = e[qn];
vector<bool> seen(n, false);
return dfs(start, l[qn], r[qn], end, seen, start >= l[qn] && start <= r[qn], start < l[qn]);
}
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
n = N; x = X; y = Y; s = S; e = E; l = L; r = R;
m = x.size(), q = S.size();
adj.assign(n, vi());
FOR(i, 0, m) {
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
vi A(q);
for (int i = 0; i < q; ++i) {
A[i] = answer_query(i);
}
return A;
}
