#include "werewolf.h"
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define pb push_back
using namespace std;
const int MAXN = 3005 ;
bool visited0[MAXN] , visited1[MAXN] ;
vector<int> adj[MAXN] ;
void dfs0(int u,int x){
visited0[u] = 1 ;
for(int v : adj[u]){
if( !visited0[v] && v <= x){
dfs0(v,x);
}
}
}
void dfs1(int u,int x){
visited1[u] = 1 ;
for(int v : adj[u]){
if( !visited1[v] && v >= x){
dfs1(v,x);
}
}
}
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 M = sz(X);
for(int i = 0 ; i < M ; i++ ){
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
int Q =sz(S);
vector<int> A(Q);
for (int i = 0; i < Q; ++i) {
A[i] = 0 ;
memset(visited1,0,sizeof visited1) ;
memset(visited0,0,sizeof visited0) ;
if(E[i]<=R[i])
dfs0(E[i],R[i]);
else
dfs1(E[i],L[i]);
if(E[i]>=L[i])
dfs1(S[i],L[i]);
else
dfs0(S[i],R[i]);
for(int j = L[i] ;j <= R[i];j++)
A[i]|= (visited0[j]&&visited1[j]);
}
return A;
}
// namespace {
// int read_int() {
// int x;
// if (scanf("%d", &x) != 1) {
// fprintf(stderr, "Error while reading input\n");
// exit(1);
// }
// return x;
// }
// } // namespace
// int main() {
// int N = read_int();
// int M = read_int();
// int Q = read_int();
// std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
// for (int j = 0; j < M; ++j) {
// X[j] = read_int();
// Y[j] = read_int();
// }
// for (int i = 0; i < Q; ++i) {
// S[i] = read_int();
// E[i] = read_int();
// L[i] = read_int();
// R[i] = read_int();
// }
// std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
// for (size_t i = 0; i < A.size(); ++i) {
// printf("%d\n", A[i]);
// }
// return 0;
// }
