#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long
template<typename T>
int len(T &a){return a.size();}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
struct DSU{
vector<int> par, sz; int n;
DSU (int _n){
n = _n;
par.resize(n);
iota(all(par), 0);
sz.assign(n, 1);
}
DSU (){}
int get(int a){
return (par[a] == a ? a : par[a] = get(par[a]));
}
void init(int _n){
n = _n;
par.resize(n);
iota(all(par), 0);
sz.assign(n, 1);
}
void unite(int a, int b){
a = get(a);
b = get(b);
if(a == b) return;
if(sz[a] < sz[b]) swap(a,b);
sz[a] += sz[b];
par[b] = a;
}
void link(int a, int b){
a = get(a); b = get(b);
if(a == b) return;
sz[b] += sz[a];
par[a] = b;
}
};
int n, m, q;
vector<vector<int>> g;
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) {
n = N;
q = len(s);
m = len(x);
vector<int> res(q);
for(int i = 0; i < m; i ++) if(x[i] > y[i]) swap(x[i], y[i]);
for(int i = 0; i < q; i ++){
DSU hum(n), wolf(n);
for(int j = 0; j < m; j ++){
if(x[j] >= l[i]){
hum.unite(y[j], x[j]);
// cout << x[j] << ' ' << y[j];
}
if(y[j] <= r[i]){
wolf.unite(x[j], y[j]);
}
}
//cout << endl;
bool ok = 0;
for(int j = l[i]; j <= r[i]; j ++){
if(hum.get(j) != hum.get(s[i])) continue;
if(wolf.get(j) != wolf.get(e[i])) continue;
ok = 1;
break;
}
res[i] = ok;
}
return res;
}
