#include "september.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
constexpr int MAX = 2e5+2, INF = 2e9;
template <typename T>
struct SegTree{
T null;
int n;
vector <T> t;
void init(int n1) {
n = n1;
null = -INF;
t.assign(4*(n+2), null); // TODO
}
T merge(T a, T b) {
T c;
if (a == null) return b;
if (b == null) return a;
c = max(a, b); // TODO
return c;
}
void build(int v, int tl, int tr, vector <T> &a) {
if (tl == tr) {
t[v] = a[tl];
return;
}
int tm = (tl + tr) / 2;
build(v*2, tl, tm, a);
build(v*2+1, tm+1, tr, a);
t[v] = merge(t[v*2], t[v*2+1]);
}
T find(int v, int tl, int tr, int l, int r) {
if (l > r) return null;
if (tl == l && r == tr) return t[v];
int tm = (tl + tr) / 2;
T resL = find(v*2, tl, tm, l, min(r, tm));
T resR = find(v*2+1, tm+1, tr, max(l, tm+1), r);
T res = merge(resL, resR);
return res;
}
void update(int v, int tl, int tr, int i, T x) {
if (tl == tr) {
t[v] = x;
return;
}
int tm = (tl + tr) / 2;
if (i <= tm) update(v*2, tl, tm, i, x);
else update(v*2+1, tm+1, tr, i, x);
t[v] = merge(t[v*2], t[v*2+1]);
}
T get(int l, int r) {
return find(1, 0, n-1, l, r);
}
void upd(int i, T x) {
update(1, 0, n-1, i, x);
}
};
vector <vector <int>> g;
vector <int> lev, e, in, out;
int te = -1;
void dfs(int u) {
in[u] = ++te;
e.pb(u);
for (int &i : g[u]) {
lev[i] = lev[u] + 1;
dfs(i);
}
out[u] = te;
}
vector <pair<int, int>> merge_rn(vector <pair<int, int>> v) {
vector <pair<int, int>> res;
sort(all(v));
for (auto &[l, r] : v) {
if (!res.empty() && l <= res.back().ss) {
res.back().ss = max(res.back().ss, r);
}
else {
res.pb({l, r});
}
}
return res;
}
int solve(int n, int m, vector<int> par, vector<vector<int>> k) {
g.clear();
g.resize(n+1);
lev.assign(n+1, 0);
in.assign(n+1, 0);
out.assign(n+1, 0);
e.clear();
te = -1;
for (auto &i : k) {
for (int &j : i) ++j;
i.pb(1);
}
for (int &i : par) i++;
for (int i = 2; i <= n; i++) {
int x = par[i-1];
g[x].pb(i);
}
dfs(1);
vector <int> v;
vector <vector <int>> pos(m, vector <int>(n+1));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
pos[i][k[i][j]] = j;
}
}
vector <pair<int, int>> rn;
for (int i = 1; i <= n; i++) {
int mn = INF, mx = -INF;
for (int j = 0; j < m; j++) {
mn = min(mn, pos[j][i]);
mx = max(mx, pos[j][i]);
}
rn.pb({mn, mx});
}
for (int z = 0; z < m; z++) {
SegTree <int> t;
t.init(n);
for (int i = 0; i < n; i++) {
t.upd(i, pos[z][e[i]]);
}
for (int i = 1; i <= n; i++) {
int l = pos[z][i];
int r = t.get(in[i], out[i]);
if (l <= r) {
rn.pb({l, r});
}
}
}
rn = merge_rn(rn);
return rn.size()-1;
}
