#include "werewolf.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
int n, m, q;
int rep[200001][2];
vector<pair<int, int> >edjes;
int findd(int u, short cual){
if(rep[u][cual] == u)return u;
return rep[u][cual] = findd(rep[u][cual], cual);
}
void joinn(int a, int b, short cual){
a = findd(a, cual);
b = findd(b, cual);
if(a == b)return ;
rep[a][cual] = b;
}
std::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;
m = X.size();
q = S.size();
for(int i = 0 ; i < m ; i ++){
edjes.pb({X[i], Y[i]});
}
vector<int>A;
for(int query = 0 ; query < q ; query ++){
for(int i = 0 ; i < n ; i ++){
rep[i][0] = i;
rep[i][1] = i;
}
for(int i = 0 ; i < m ; i ++){
if(X[i] <= R[query] and Y[i] <= R[query]){
joinn(X[i], Y[i], 0);
}
if(X[i] >= L[query] and Y[i] >= L[query]){
joinn(X[i], Y[i], 1);
}
}
bool posible = false;
S[query] = findd(S[query], 1);
E[query] = findd(E[query], 0);
for(int i = L[query] ; i <= R[query] ; i ++){
if(findd(i, 1) == S[query] and findd(i, 0) == E[query]){
posible = true;
break;
}
}
if(posible)A.pb(1);
else A.pb(0);
}
return A;
}
