// #define LOCAL 1
#include <bits/stdc++.h>
#ifndef LOCAL
#include "werewolf.h"
#endif
using namespace std;
#define REP(i, n) for (int i = 0; i < (n); i++)
bool reachable(vector<vector<int>>& adjList, int start, int end, int lo, int hi) {
const int N = adjList.size();
vector<bool> vis(N, false);
queue<int> q;
if (start >= lo && start <= hi) {
q.push(start);
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto& v : adjList[u]) {
if (lo <= v && v <= hi && !vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
return vis[end];
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
const int Q = L.size();
const int M = X.size();
vector<vector<int>> adj(N);
REP(i, M) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
vector<int> r(Q, 0);
REP(i, Q) {
REP(u, N) {
bool reach_S = reachable(adj, S[i], u, L[i], N-1);
bool reach_E = reachable(adj, E[i], u, 0, R[i]);
r[i] |= reach_S && reach_E;
if (r[i]) {break;}
}
}
return r;
}
#ifdef LOCAL
int main() {
int N = 6;
vector<int> X{5,1,1,3,3,5};
vector<int> Y{1,2,3,4,0,2};
vector<int> S{4,4,5};
vector<int> E{2,2,4};
vector<int> L{1,2,3};
vector<int> R{2,2,4};
auto r = check_validity(N, X, Y, S, E, L, R);
for_each(r.begin(), r.end(), [](int x) {cout << x << ' ';});
cout << '\n';
return 0;
}
#endif
