#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;
struct IT{
int n;
vi T;
IT () {};
IT(int _n){
int k = 1;
n = _n;
while (2 * k <= n) k *= 2;
T.resize(4 * k, 0);
}
void update(int id, int l, int r, int pos, int val){
if(l == r){
T[id] = val;
return;
}
int m = (l + r)/2;
if (pos <= m) update(id*2, l, m, pos, val);
else update(id*2+1, m+1, r, pos, val);
T[id] = max(T[id*2], T[id*2+1]);
}
int get(int id, int l, int r, int u, int v){
if (l > v || r < u) return 0;
if (u <= l && r <= v) return T[id];
int m = (l + r)/2;
return max(get(id*2, l, m, u, v), get(id*2+1, m+1, r, u, v));
}
};
mt19937 rd(time(0));
int Rand(int l, int r){
return l + (rd()%(r - l + 1) + r - l + 1) %(r - l + 1);
}
int n, m, in[N], ou[N], timer, v[N];
vector<int> G[N];
void dfs(int u, int par){
in[u] = ++timer;
for (int &v : G[u]){
if(v == par) continue;
dfs(v, u);
}
ou[u] = timer;
}
int solve(int _n, int _m, vector<int> F, vector<vi> S){
n = _n; m = _m;
FOR (i, 1, n - 1){
G[i].pb(F[i]);
G[F[i]].pb(i);
}
dfs(0, -1);
vector<IT> seg(m);
vector<int> pos(n, 0);
FOR (i, 0, m - 1) {
seg[i] = IT(n);
FOR (j, 0, n - 2){
pos[S[i][j]] = max(pos[S[i][j]], j);
seg[i].update(1, 1, n, in[S[i][j]], j);
}
}
int last = -1;
vector<ii> a;
FOR (i, 0, n - 2){
int mx = 0;
FOR (j, 0, m - 1){
mx = max(mx, seg[j].get(1, 1, n, in[S[j][i]], ou[S[j][i]]));
mx = max(mx, pos[S[j][i]]);
}
if (last < i){
a.pb({i, mx});
} else {
assert(a.size());
a.back().se = max(last, mx);
}
last = max(last, mx);
}
// FOR (i, 0, n - 1) v[i] = Rand(0, 1e9);
// vector<vector<long long>> pref(m, vector<long long>(n, 0));
// vector<vector<long long>> arr(m, vector<long long>(n, 0));
// FOR (i, 0, m - 1){
// pref[i][0] = v[S[i][0]];
// FOR (j, 1, n - 2) pref[i][j] = pref[i][j-1] + v[S[i][j]];
// FOR (j, 0, (int)a.size() - 1){
// arr[i][j] = pref[i][a[j].se] - pref[i][a[j].fi] + v[S[i][a[j].fi]];
// }
// }
FOR (i, 0, n - 1){
G[i].clear();
in[i] = ou[i] = 0;
}
timer = 0;
return a.size();
// vector<int> dp(a.size() + 2, 0);
// dp[0] = 0;
// FOR (i, 1, (int)a.size()){
// vector<int> s(m);
// FORD(j, i, 1){
// FOR (z, 0, m - 1) s[z] += arr[z][j - 1];
// int ok = 1;
// FOR (i, 0, m - 2) if (s[i] != s[i+1]) ok = 0;
// if (ok) dp[i] = max(dp[i], dp[j-1] +1 );
// }
// }
// FOR (i, 0, n - 1){
// G[i].clear();
// in[i] = ou[i] = 0;
// }
// timer = 0;
//
// return dp[a.size()];
}
#ifdef _Pbrngw_
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
cout << solve(5, 2, {-1, 0, 0, 1, 1}, {{1, 2, 3, 4}, {4, 1, 2, 3}}) << '\n';
cout << solve(3, 1, {-1, 0, 0 }, {{2, 3}}) << '\n';
return 0;
}
#endif // _Pbrngw_
