#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll f[2][N];
enum state{ human,wolf };
ll Find(ll x,ll sat){
if(f[sat][x]<0) return x;
else return f[sat][x]=Find(f[sat][x],sat);
}
void Union(ll x,ll y,ll sat){
x=Find(x,sat),y=Find(y,sat);
if(x==y) return;
f[sat][y]=x;
}
vector<int> check_validity(int n, vector<int> u, vector<int> v, vector<int> s, vector<int> e,vector<int> l, vector<int> r) {
ll q = s.size(),m=u.size();
vector<int> ans;
for(ll kase=0;kase<q;kase++){
for(ll i=0;i<n;i++) f[human][i]=f[wolf][i]=-1;
for(ll i=0;i<m;i++){
if(u[i]<=r[kase] && v[i]<=r[kase]) Union(u[i],v[i],wolf);
if(u[i]>=l[kase] && v[i]>=l[kase]) Union(u[i],v[i],human);
}
ll flag=0;
for(ll i=l[kase];i<=r[kase];i++){
if(Find(s[kase],human)==Find(i,human) && Find(i,wolf)==Find(e[kase],wolf)){
flag=1;
break;
}
}
// printf("%lld\nwolf:",kase);
// for(ll i=0;i<n;i++){
// if(Find(s[kase],wolf)==Find(i,wolf)) printf("%lld ",i);
// }cout<<endl;
// printf("human:");
// for(ll i=0;i<n;i++){
// if(Find(i,human)==Find(e[kase],human)) printf("%lld ",i);
// }cout<<endl;
ans.push_back(flag);
}
return ans;
}
