#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int N = 200010;
const int LOGN = 20;
vector <int> g[N];
vector <int> g1[N], g2[N];
int tmm;
int tin[N][2], tout[N][2];
int pai[N][LOGN][2];
struct DSU{
int pai[N], sz[N];
stack <int> s;
DSU(){
for(int i = 0;i < N;i++){
pai[i] = i;
sz[i] = 1;
}
}
void clear(int n){
for(int i = 0;i < n;i++){
pai[i] = i;
sz[i] = 1;
}
}
int find(int x){
return pai[x] = (x == pai[x] ? x : find(pai[x]));
}
void join(int a, int b){
a = find(a);
b = find(b);
if(a == b) {
return;
}
pai[a] = b;
sz[b] += sz[a];
}
} dsu;
void constructG1(int n){
dsu.clear(n);
for(int i = n-1;i >= 0;i--){
for(auto x : g[i]){
if(x < i) continue;
if(dsu.find(x) == i) continue;
g1[i].push_back(dsu.find(x));
g1[dsu.find(x)].push_back(i);
dsu.join(dsu.find(x), i);
}
}
}
void constructG2(int n){
dsu.clear(n);
for(int i = 0;i < n;i++){
for(auto x : g[i]){
if(x > i) continue;
if(dsu.find(x) == i) continue;
g2[i].push_back(dsu.find(x));
g2[dsu.find(x)].push_back(i);
dsu.join(dsu.find(x), i);
}
}
}
vector <int> v1, v2;
void dfs1(int v, int p){
pai[v][0][0] = p;
tin[v][0] = tmm;
v1.push_back(v);
tmm++;
for(auto x : g1[v]){
if(x == p) continue;
dfs1(x, v);
}
tout[v][0] = tmm;
}
void dfs2(int v, int p){
pai[v][0][1] = p;
tin[v][1] = tmm;
tmm++;
v2.push_back(v);
for(auto x : g2[v]){
if(x == p) continue;
dfs2(x, v);
}
tout[v][1] = tmm;
}
struct Segtree{
int tree[4*N];
int join(int a, int b){
return max(a, b);
}
void build(int node, int l, int r){
if(l == r){
tree[node] = -1;
return;
}
int mid = (l+r)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
tree[node] = -1;
return;
}
void update(int node, int l, int r, int pos, int val){
if(l == r){
tree[node] = val;
return;
}
int mid = (l+r)/2;
if(l <= pos and pos <= mid) update(2*node, l, mid, pos, val);
else update(2*node+1, mid+1, r, pos, val);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
int query(int node, int l, int r, int tl, int tr){
if(l > tr or tl > r) return 0;
if(l <= tl and tr <= r) return tree[node];
int mid = (tl+tr)/2;
return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
}
} seg;
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 m = X.size();
for(int i = 0;i < m;i++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
constructG1(n);
constructG2(n);
tmm = 0;
dfs1(0, 0);
tmm = 0;
dfs2(n-1, n-1);
for(int bit = 1;bit < LOGN;bit++){
for(int i = 0;i < n;i++){
for(int j = 0;j < 2;j++){
pai[i][bit][j] = pai[pai[i][bit-1][j]][bit-1][j];
}
}
}
vector <int> query[2];
for(int i = 0;i < S.size();i++){
int s = S[i], mn = L[i];
if(s < L[i]){
query[0].push_back(-1);
}
for(int bit = LOGN-1;bit >= 0;bit--){
if(pai[s][bit][0] >= mn) s = pai[s][bit][0];
}
query[0].push_back(s);
}
for(int i = 0;i < E.size();i++){
int s = E[i], mn = R[i];
if(s > mn){
query[1].push_back(-1);
}
for(int bit = LOGN-1;bit >= 0;bit--){
if(pai[s][bit][1] <= mn) s = pai[s][bit][1];
}
query[1].push_back(s);
}
vector <array <int, 4>> v;
map <array <int, 4>, int> responder;
map <int, int> ans;
for(int i = 0;i < query[0].size();i++){
int s = query[0][i], e = query[1][i];
if(s == -1 or e == -1){
ans[i] = 0;
continue;
}
v.push_back({tout[s][0]-1, tin[s][0], tin[e][1], tout[e][1]});
responder[{tout[s][0]-1, tin[s][0], tin[e][1], tout[e][1]}] = i;
}
sort(v.begin(), v.end());
vector <pair <int, int>> comprimir;
map <int, int> aux;
for(int i = 0;i < v2.size();i++){
aux[v2[i]] = i;
}
for(auto &x : v1){
x = aux[x];
} int at = 0;
seg.build(1, 1, n);
for(auto [b, a, c, d] : v){
while(at <= b){
seg.update(1, 1, n, v1[at]+1, at);
at++;
}
int res = seg.query(1, c+1, d+1, 1, n);
if(res < a) ans[responder[{b, a, c, d}]] = 0;
else ans[responder[{b, a, c, d}]] = 1;
}
vector <int> resp;
for(int i = 0;i < query[0].size();i++){
resp.push_back(ans[i]);
}
return resp;
}
