#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)
template<typename T>
using v = vector<T>;
const int MOD = 1e9+7;
v<v<int>> adj;
v<v<bool>> vis;
int l, r;
bool can;
int e;
bool check(int x, int t) {
if (t == 0) {
return (x >= l);
}
else {
return x <= r;
}
}
void dfs(int n, int t) {
vis[n][t] = true;
if (n == e) can = true;
for (auto x : adj[n]) {
if (vis[x][t] == false && check(x, t)) {
dfs(x, t);
}
if (t == 0 && l <= n && n <= r) {
if (vis[x][1] == false && check(x, 1)) dfs(x, 1);
}
}
}
v<int> check_validity(int N, v<int> X, v<int> Y, v<int> S, v<int> E, v<int> L, v<int> R) {
int n = N;
adj.resize(n);
int m = X.size();
rep(i, 0, m){
int a = X[i], b = Y[i];
adj[a].push_back(b);
adj[b].push_back(a);
}
int q = L.size();
v<int> ans(q);
rep(i, 0, q) {
vis.assign(n, v<bool>(2, false));
l = L[i], r = R[i];
e = E[i];
can = false;
dfs(S[i], 0);
if (can) ans[i] = 1;
else ans[i] = 0;
}
return ans;
}
