#include "september.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct segment {
int t[N * 4];
void upd (int l, int r, int idx, int pos, int val) {
if (l == r) return void(t[idx] = max(t[idx], val));
int mid = (l + r) >> 1;
if (pos <= mid) upd(l, mid, idx * 2 + 1, pos, val);
else upd(mid + 1, r, idx * 2 + 2, pos, val);
t[idx] = max(t[idx * 2 + 1], t[idx * 2 + 2]);
}
int qr (int l, int r, int idx, int tl, int tr) {
if (l > tr || r < tl) return 0;
if (l >= tl && r <= tr) return t[idx];
int mid = (l + r) >> 1;
return max(qr(l, mid, idx * 2 + 1, tl, tr), qr(mid + 1, r, idx * 2 + 2, tl, tr));
}
};
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
int n = N, m = M;
vector<vector<int>> v(n, vector<int>());
vector<vector<int>> pos(m, vector<int>(n));
vector<vector<int>> rpos(m, vector<int>(n));
vector<segment> segm(m);
int t = -1;
for (int i = 1; i < n; i++) {
v[F[i]].emplace_back(i);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n - 1; j++) {
pos[i][S[i][j]] = j;
}
}
auto dfs = [&] (auto &&dfs, int cur, int par) -> void {
for (auto &e: v[cur]) {
if (par == e) continue;
dfs(dfs, e, cur);
for (int i = 0; i < m; i++) {
pos[i][cur] = max(pos[i][cur], pos[i][e]);
}
}
};
dfs(dfs, 0, -1);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n - 1; j++) {
segm[i].upd(0, n - 2, 0, j, pos[i][S[i][j]]);
}
}
for (int i = 0; i < m; i++) {
for (int j = n - 2; j >= 0; j--) {
rpos[i][j] = segm[i].qr(0, n - 2, 0, j, pos[i][S[i][j]]);
segm[i].upd(0, n - 2, 0, j, rpos[i][j]);
}
}
int ans = 0;
vector<int> ptr(m);
for (int i = 0; ; i++) {
int mx = -1;
for (int j = 0; j < m; j++) {
mx = max(mx, rpos[j][ptr[j]]);
}
for (int j = 0; j < m; j++) {
ptr[j] = mx + 1;
}
ans++;
if (mx + 1 >= n - 1) break;
}
return ans;
return 0;
}
