#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 3e3 + 10;
vector<int> g[mxn];
struct State {
int pos, lastT;
bool transform;
};
bool pos(int start, int end, int l, int r) {
if (start < l) return 0;
bool visited[mxn];
memset(visited, 0, sizeof(visited));
queue<State> q;
q.push({start, (start <= r), 0});
visited[start] = 1;
while (q.size()) {
auto cur = q.front();
q.pop();
if (cur.pos == end) {
return (cur.transform || cur.lastT);
}
for (auto x : g[cur.pos]) {
if (!visited[x]) {
if (cur.transform) {
if (x <= r) {
visited[x] = 1;
q.push({x, 0, 1});
}
}
else {
if (x >= l) {
visited[x] = 1;
if (x <= r) q.push({x, 1, 0});
else q.push({x, 0, 0});
}
else {
if (cur.lastT) {
q.push({x, 0, 1});
visited[x] = 1;
}
}
}
}
}
}
return 0;
}
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 Q = S.size();
vector<int> A(Q);
for (int i = 0; i < N - 1; i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
for (int i = 0; i < Q; i++) {
A[i] = pos(S[i], E[i], L[i], R[i]);
}
return A;
}
