#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int mxn = 3030;
int n, m, q, par[mxn];
int parent(int u) { return par[u] < 0 ? u : par[u] = parent(par[u]); }
bool unite(int u, int v, string debug = "") {
if(debug.size()) {
cout << debug << ": " << u << ' ' << v << endl;
}
u = parent(u);
v = parent(v);
if(u == v) return 0;
if(par[u] > par[v]) swap(u, v);
par[u] += par[v];
par[v] = u;
return 1;
}
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
n = N;
m = X.size();
q = S.size();
vi ret;
for(int i = 0; i < q; i++) {
int s = S[i];
int e = E[i];
int l = L[i];
int r = R[i];
memset(par, -1, sizeof(int) * n);
for(int i = 0; i < m; i++) {
if(X[i] >= l && Y[i] >= l)
unite(X[i], Y[i]);
}
bitset<mxn> st = 0;
for(int i = l; i <= r; i++)
if(parent(i) == parent(s))
st[i] = 1;
memset(par, -1, sizeof(int) * n);
for(int i = 0; i < m; i++) {
if(X[i] <= r && Y[i] <= r)
unite(X[i], Y[i]);
}
bitset<mxn> en = 0;
for(int i = 0; i < n; i++)
if(parent(i) == parent(e))
en[i] = 1;
bitset<mxn> cnt = st & en;
if(cnt.count())
ret.push_back(1);
else
ret.push_back(0);
}
return ret;
}
/*
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
*/
