#include "september.h"
#include <vector>
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
int n, m;
vector < int > g[maxn];
int tmr;
int pos[maxn];
int a[maxn], label[maxn];
int tin[maxn], tout[maxn];
void dfs(int beg, int from)
{
tmr ++;
a[tmr] = pos[beg];
label[beg] = tmr;
tin[beg] = tmr;
for (auto nb: g[beg])
{
if(nb == beg)continue;
dfs(nb, beg);
}
tout[beg] = tmr;
}
int t[maxn * 4];
void build(int i, int l, int r)
{
if(l == r)
{
t[i] = a[l];
return;
}
int mid = (l + r)/2;
build(2*i, l, mid);
build(2*i+1, mid+1, r);
t[i] = max(t[2*i], t[2*i+1]);
}
int upos, uval;
void update(int i, int l, int r)
{
if(l == r)
{
t[i] = uval;
a[l] = uval;
return;
}
int mid = (l + r)/2;
if(upos <= mid)update(2*i, l, mid);
else update(2*i+1, mid+1, r);
t[i] = max(t[2*i], t[2*i+1]);
}
int ql, qr;
int query(int i, int l, int r)
{
if(qr < l || ql > r)return 0;
if(ql <= l && r <= qr)return t[i];
int mid = (l + r)/2;
return max(query(2*i, l, mid), query(2*i+1, mid+1, r));
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S)
{
n = N;
m = M;
for (int i = 0; i < n; ++ i)
g[i].clear();
for (int i = 0; i < n; ++ i)
{
int par = F[i];
if(par != -1)g[par].pb(i);
}
for (int i = 0; i < m; ++ i)
{
for (int j = 0; j < n-1; ++ j)
{
int x = S[i][j];
pos[x] = j;
}
}
tmr = -1;
dfs(0, -1);
build(1, 1, tmr);
int mx = 0;
int day = 0;
for (int d = 0; d < M; ++ d)
{
mx = 0;
day = 0;
int st = 0;
for (int i = 0; i < S[0].size(); ++ i)
{
int v = S[0][i];
ql = tin[v];
qr = tout[v];
int nxt = query(1, 1, tmr);
mx = max(mx, nxt);
if(mx == i)
{
int rgl = st, rgr = i;
for (int k = rgr; k <= rgr; ++ k)
{
upos = label[k];
uval = rgr;
update(1, 1, tmr);
}
day ++;
mx = i + 1;
st = i + 1;
}
}
}
return day;
}
