#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, m;
vector <int> g[maxn];
int s[10][maxn];
int far[10][maxn];
int pos[maxn];
int dp[maxn];
vector <int> sorted[10];
void dfs (int u, int p, int min_id, int type) {
far[type][u] = min_id;
for (int &v : g[u]) {
dfs(v, u, min(min_id, pos[u]), type);
}
}
void build (int id_ver) {
for (int i = 0; i < n - 1; i++) pos[s[id_ver][i]] = i;
pos[0] = 2e9;
dfs(0, 0, 2e9, id_ver);
}
int solve (int N, int M, vector <int> F, vector <vector <int>> S) {
n = N;
m = M;
for (int i = 0; i < n; i++) {
int u = F[i];
if (u == - 1) continue;
g[u].push_back(i);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n - 1; j++) s[i][j] = S[i][j];
}
for (int i = 0; i < m; i++) {
build(i);
}
auto check = [&] (int l, int r, int m) {
for (int i = 0; i < m; i++) {
sort(sorted[i].begin(), sorted[i].end());
}
for (int i = 1; i < m; i++) {
if (sorted[i] != sorted[0]) return 0;
}
for (int i = 0; i < m; i++) {
for (int j = l; j <= r; j++) {
int u = s[i][j];
if (far[i][u] < l) return 0;
}
}
return 1;
};
for (int i = 0; i < n; i++) {
g[i].clear();
dp[i] = - 1;
}
dp[0] = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < m; j++) {
sorted[j].clear();
}
for (int j = i; j > 0; j--) {
for (int t = 0; t < m; t++) {
sorted[t].push_back(s[t][j]);
}
if (check(j - 1, i - 1, m)) {
dp[i] = max(dp[i], dp[j - 1] + 1);
}
}
}
return dp[n - 1];
}
