#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
typedef int64_t ll;
typedef int32_t ii;
//~ #define int ll
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 = x.size();
int q = s.size();
vector<vector<int>> edges(n);
for(int i=0;i<m;i++){
edges[x[i]].push_back(y[i]);
edges[y[i]].push_back(x[i]);
}
if(n <= 3000 && m <= 6000 && q <= 3000){
vector<int> used_s(n), used_e(n);
function<void(vector<int>&, int, int, int)> dfs = [&](vector<int>& used, int u, int l, int r){
used[u] = 1;
for(auto x : edges[u]){
if(!used[x] && l <= x && x <= r){
dfs(used, x, l, r);
}
}
};
vector<int> ans(q);
for(int i=0;i<q;i++){
fill(used_s.begin(), used_s.end(), 0);
fill(used_e.begin(), used_e.end(), 0);
dfs(used_s, s[i], l[i], n);
dfs(used_e, e[i], 0, r[i]);
//~ for(int j=0;j<n;j++){
//~ cout<<used_s[j]<<" ";
//~ } cout<<"\n";
//~ for(int j=0;j<n;j++){
//~ cout<<used_e[j]<<" ";
//~ } cout<<"\n";
for(int j=0;j<n;j++){
if(used_s[j] && used_e[j]){
ans[i] = 1;
break;
}
}
}
return ans;
}
assert(false);
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
2 5
4 2 1 2
4 2 2 2
5 4 3 4
*/
