#include <bits/stdc++.h>
#define bug cout << "bug" << endl;
using namespace std;
using ll = long long;
const int N = 1e5 + 5, mod = 1e9 + 7;
const ll inf = 9e18;
int n, m, ans, f[N], s[6][N], st[6][4*N], tin[N], tout[N], id[N], timer;
bool seen[N], see[6][N];
vector <int> g[N];
queue <int> q[6];
void dfs(int u) {
tin[u] = ++timer;
for (int v : g[u]) dfs(v);
tout[u] = timer;
}
void update(int id, int x, int l, int r, int ind) {
if (l == r) {
st[id][x] = 1;
}
else {
int mid = (l + r) >> 1;
if (ind <= mid) update(id, x<<1, l, mid, ind);
else update(id, x<<1|1, mid + 1, r, ind);
st[id][x] = st[id][x<<1] + st[id][x<<1|1];
}
}
int query(int id, int x, int l, int r, int i, int j) {
if (l > j || r < i) return 0;
if (l >= i && r <= j) return st[id][x];
int mid = (l + r) >> 1;
return query(id, x<<1, l, mid, i, j) + query(id, x<<1|1, mid + 1, r, i, j);
}
int solve(int N, int M, vector <int> F, vector <vector <int>> S) {
n = N;
m = M;
timer = ans = 0;
for (int i = 0; i < n; ++i) g[i].clear();
fill(id, id + m + 1, 0);
fill(seen, seen + n + 1, 0);
for (int j = 0; j < m; ++j) {
for (int i = 0; i < n - 1; ++i) s[j][i] = S[j][i];
fill(st[j], st[j] + 4*n + 1, 0);
fill(see[j], see[j] + n + 1, 0);
}
for (int i = 0; i < n; ++i) {
f[i] = F[i];
if (f[i] != -1) g[f[i]].push_back(i);
}
dfs(0);
int ptr = -1;
while (true) {
ans++;
ptr++;
for (int j = 0; j < m; ++j) {
int u = s[j][ptr];
see[j][u] = 1;
if (seen[u]) id[j]--;
else {
seen[u] = 1;
for (int i = 0; i < m; ++i) if (!see[i][u]) id[i]++;
}
q[j].push(u);
update(j, 1,1,n, tin[u]);
}
while (true) {
for (int j = 0; j < m; ++j) {
while (!q[j].empty()) {
int u = q[j].front();
if (query(j, 1,1,n, tin[u], tout[u]) == tout[u] - tin[u] + 1) q[j].pop();
else break;
}
}
int ok = 0;
for (int j = 0; j < m; ++j) {
if (!q[j].empty()) ok = 1;
ok = max(ok, id[j]);
}
if (ok == 0) break;
ptr++;
for (int j = 0; j < m; ++j) {
int u = s[j][ptr];
see[j][u] = 1;
if (seen[u]) id[j]--;
else {
seen[u] = 1;
for (int i = 0; i < m; ++i) if (!see[i][u]) id[i]++;
}
q[j].push(u);
update(j, 1,1,n, tin[u]);
}
}
if (ptr == n - 2) break;
}
return ans;
}
