#include <bits/stdc++.h>
#include "werewolf.h"
#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
const ll N = 2e5 + 1;
template <typename T> void vout(T s){cout << s << endl;exit(0);}
vector <int> v[N];
int tin[N + 1], tout[N + 1], stn;
int tin1[N + 1], tout1[N + 1], stn1;
vector <int> Up[N], Down[N];
int t[4 * N], pos[N], p[N], pt[N];
void dfs(int x, int p){
tin[x] = ++stn;
for(int to : Up[x])if(to != p)dfs(to, x);
tout[x] = stn;
}
void go(int x, int p){
tin1[x] = ++stn1;
pos[tin1[x]] = tin[x];
pt[tin[x]] = tin1[x];
for(int to : Down[x])if(to != p)go(to, x);
tout1[x] = stn1;
}
void build(int v, int tl, int tr){
if(tl == tr)t[v] = pos[tl]; else{
int tm = (tl + tr) >> 1;
build(v << 1, tl, tm);
build((v << 1) + 1, tm + 1, tr);
t[v] = min(t[v << 1], t[(v << 1) + 1]);
}
}
void modify(int v, int tl, int tr, int pos){
if(tl == tr)t[v] = 1e9; else{
int tm = (tl + tr) >> 1;
if(pos <= tm)modify(v << 1, tl, tm, pos);
else modify((v << 1) + 1, tm + 1, tr, pos);
t[v] = min(t[v << 1], t[(v << 1) + 1]);
}
}
int get(int v, int tl, int tr, int l, int r){
if(l > r)return 1e9;
if(tl == l && tr == r)return t[v];
int tm = (tl + tr) >> 1;
return min(get(v << 1, tl, tm, l, min(r, tm)), get((v << 1) + 1, tm + 1, tr, max(l, tm + 1), r));
}
int get(int x){
if(p[x] != x)p[x] = get(p[x]);
return p[x];
}
vector <int> vq[N];
vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r){
int q = s.size(), m = x.size();
vi ans(q);
for(int &i : x)i++;
for(int &i : y)i++;
for(int &i : s)i++;
for(int &i : e)i++;
for(int &i : l)i++;
for(int &i : r)i++;
for(int i = 0; i < m; i++){
v[x[i]].p_b(y[i]);
v[y[i]].p_b(x[i]);
}
for(int i = 0; i < q; i++)vq[l[i]].p_b(i);
for(int i = 1; i <= n; i++)p[i] = i;
int old;
for(int i = n; i > 0; i--){
for(int j : v[i])if(j > i){
if(get(j) != i){
old = get(j);
p[get(j)] = i;
Up[old].p_b(i);
Up[i].p_b(old);
}
}
for(int j : vq[i]){
l[j] = get(s[j]);
}
vq[i].clear();
}
for(int i = 1; i <= n; i++)p[i] = i;
for(int i = 0; i < q; i++)vq[r[i]].p_b(i);
for(int i = 1; i <= n; i++){
for(int j : v[i])if(j < i){
if(get(j) != i){
old = get(j);
p[get(j)] = i;
Down[old].p_b(i);
Down[i].p_b(old);
}
}
for(int j : vq[i]){
r[j] = get(e[j]);
}
vq[i].clear();
}
dfs(1ll, 0ll);
go(n, 0ll);
build(1, 1, n);
vector <pii> Q;
for(int i = 0; i < q; i++){
if(s[i] < l[i])continue;
if(e[i] > r[i])continue;
Q.p_b({tin[l[i]], i});
}
if(Q.empty())return ans;
sort(all(Q));
int uk = 1;
for(pii kek : Q){
while(uk < kek.fi){
modify(1, 1, n, pt[uk++]);
}
if(get(1, 1, n, tin1[r[kek.se]], tout1[r[kek.se]]) <= tout[l[kek.se]])ans[kek.se] = 1;
}
return ans;
}
