#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) (int)(v).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 2e5+7;
vector <vector <int>> graph(N);
vector <int> eq, vis, belong, cluster, can, can2;
int n, q, clcnt;
void go(int v, int cond){
vis[v] = 1;
if(cluster[belong[v]] == 1){
if(!cond) can[belong[v]] = 1;
else can2[belong[v]] = 1;
}
for(auto to : graph[v]){
if(!vis[to] && (cond != cluster[belong[to]])){
go(to, cond);
}
}
}
void findcl(int v){
cluster[clcnt] = eq[v];
belong[v] = clcnt;
vis[v] = 1;
for(auto to : graph[v]){
if(!vis[to] && eq[to] == eq[v]){
findcl(to);
}
}
}
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 i, j;
n = N, q = sz(S);
vector <int> ans(q);
for(i = 0; i < sz(X); i++){
graph[X[i]].pb(Y[i]);
graph[Y[i]].pb(X[i]);
}
for(j = 0; j < q; j++){
eq = vis = belong = cluster = can = can2 = vector <int> (n);
for(i = 0; i < n; i++){
if(i < L[j]) eq[i] = 0;
else if(i > R[j]) eq[i] = 2;
else eq[i] = 1;
}
clcnt = 0;
for(i = 0; i < n; i++){
if(!vis[i]){
findcl(i);
clcnt++;
}
}
if(cluster[belong[S[j]]] == 0 || cluster[belong[E[j]]] == 2){
continue;
}
for(i = 0; i < n; i++) vis[i] = 0;
go(S[j], 0);
for(i = 0; i < n; i++) vis[i] = 0;
go(E[j], 2);
for(i = 0; i < clcnt; i++){
if(can[i] && can2[i]){
ans[j] = 1;
break;
}
}
}
return ans;
}
/*
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
*/
