#include "werewolf.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
using namespace std;
vector < vector <int> > g;
const int N = 3005;
int n, m, u[2][N];
void dfs (int v, int type, int l, int r)
{
u[type][v] = 1;
for (auto to : g[v])
{
if (u[type][to] || to < l || to > r) continue;
dfs(to, type, l, r);
}
}
vector<int> check_validity(int N, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r)
{
n = N;
m = x.size();
g.resize(n + 1);
for (int i = 0; i < m; i++)
g[ x[i] ].pb( y[i] ),
g[ y[i] ].pb( x[i] );
int q = s.size();
vector <int> ans;
for (int i = 0; i < q; i++)
{
memset(u, 0, sizeof(u));
dfs(s[i], 0, l[i], n - 1);
dfs(e[i], 1, 0, r[i]);
bool fl = 0;
for (int j = 0; j < n; j++){
if (u[0][j] && u[1][j])
fl = 1;
}
ans.pb(fl);
}
return ans;
}
