#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1,(n))
#define f first
#define s second
#define pb push_back
typedef vector<int> vi;
typedef pair<int, int> pii;
const int MAXN = 200100;
bool vis[MAXN];
bool ok = false;
vi adj[MAXN];
int cnt[MAXN];
void dfs (int v, int l, int r) {
vis[v] = true;
cnt[v]++;
for (int u : adj[v]) {
if (l <= u && u <= r && !vis[u])
dfs(u, l, r);
}
}
std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
int Q = S.size();
int m = (int)X.size();
std::vector<int> A(Q);
FOR(i, 0, m-1) {
int u = X[i], v = Y[i];
adj[u].pb(v);
adj[v].pb(u);
}
for (int i = 0; i < Q; ++i) {
ok = false;
FOR(j, 0, n-1) cnt[j] = 0;
FOR(j, 0, n-1) vis[j] = 0;
dfs (S[i], L[i], n-1);
FOR(j, 0, n-1) vis[j] = 0;
dfs (E[i], 0, R[i]);
FOR(j, 0, n-1) if (cnt[j] > 1) ok = true;
A[i] = ok;
//cout << " ans: " << A[i] << endl;
}
return A;
}
