#include "werewolf.h"
#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define vll vector<ll>
#define ins insert
#define lb lower_bound
#define ub upper_bound
using namespace std;
const ll N=2e5+5;
const ll inf=1e9;
vector<vll> G(N);
struct dsu{
vector<vll> g;
vll tin, tout;
vll p, pr;
ll tiktak;
ll n;
bool inc;
dsu(ll N, ll f){
n = N;
inc = f;
tiktak = -1;
tin.resize(n);
tout.resize(n);
pr.resize(n);
g.resize(n);
p.resize(n);
for(ll i=0;i<n;i++) p[i] = i;
}
ll anc(ll a){
return (p[a] == a ? a : p[a] = anc(p[a]));
}
bool f(ll a, ll b){
return inc ? a < b : a > b;
}
bool uni(ll a, ll b){
a = anc(a), b = anc(b);
if(a == b) return false;
if(f(a, b)) swap(a, b);
p[b] = a;
g[a].pb(b);
return true;
}
void build(vll s, vll l){
ll i, q = s.size();
vector<vll> qu(n);
for(i=0;i<q;i++){
qu[l[i]].pb(i);
}
if(inc) i = 0;
else i = n - 1;
while(i>=0 && i<n){
for(auto to : G[i]){
if((inc && to < i ) || (!inc && to > i)){
uni(to, i);
}
}
for(auto j : qu[i]){
pr[j] = anc(s[j]);
}
//iteration
i += inc ? 1 : -1;
}
}
void dfs(ll v){
tin[v] = ++tiktak;
for(auto i : g[v]) dfs(i);
tout[v] = tiktak;
}
};
vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
ll i;
ll m = X.size();
ll q = S.size();
for(i=0;i<m;i++){
G[X[i]].pb(Y[i]);
G[Y[i]].pb(X[i]);
}
dsu s(n, 0);
dsu t(n, 1);
s.build(S, L);
t.build(E, R);
s.dfs(0);
t.dfs(n-1);
vector<vll> qu(n);
for(i=0;i<q;i++){
qu[s.pr[i]].pb(i);
}
vll ans(q);
vector<set<ll>> st(n);
function<void(int)> dfs = [&](ll v){
st[v].ins(t.tin[v]);
for(auto i : s.g[v]){
dfs(i);
if(st[v].size() < st[i].size()) swap(st[i], st[v]);
for(auto j : st[i]){
st[v].ins(j);
}st[i].clear();
}
for(auto i : qu[v]){
int l = t.tin[t.pr[i]], r = t.tout[t.pr[i]];
ans[i] = (st[v].lb(l) != st[v].ub(r));
}
};
dfs(0);
return ans;
}
