#include "werewolf.h"
#include<iostream>
#include<queue>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define qq queue<pi>
#define ti tuple<int, int>
//#define G(a, b) get<a>(b)
vvi Adj;
bool oink(int a, int b, int l, int r) {
vi M(Adj.size(), 0);
if (a == b) return 1;
qq Q;
Q.push({a, 1});
Q.push({b, 2});
while (!Q.empty()) {
int c = Q.front().first, d = Q.front().second;
Q.pop();
if (d == 1 && c < l) continue;
if (d == 2 && c > r) continue;
if (M[c] != 0) {
if (M[c] == d) continue;
return 1;
}
M[c] = d;
for (auto i : Adj[c]) {
Q.push({i, d});
}
}
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();
Adj = vvi(N);
//cerr << "Adj start" << endl;
for (int i = 0; i < X.size(); i++) {
Adj[X[i]].push_back(Y[i]);
Adj[Y[i]].push_back(X[i]);
}
//cerr << "Adj end" << endl;
vector<int> A(Q);
for (int i = 0; i < Q; ++i) {
A[i] = oink(S[i], E[i], L[i], R[i]);
}
return A;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
