#include "september.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=1e5+5;
int in[nx], out[nx], t, n, st, rv[nx], cnt;
vector<int> d[nx], k;
struct segtree
{
int d[4*nx];
void build(int l, int r, int i)
{
d[i]=0;
if (l==r) return;
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
}
void update(int l, int r, int i, int idx, int vl)
{
if (idx<l||r<idx) return;
if (l==r) return d[i]=max(d[i], vl), void();
int md=(l+r)/2;
update(l ,md, 2*i, idx ,vl);
update(md+1, r, 2*i+1, idx, vl);
d[i]=max(d[2*i], d[2*i+1]);
}
int query(int l, int r, int i, int ql, int qr)
{
if (qr<l||r<ql) return 0;
if (ql<=l&&r<=qr) return d[i];
int md=(l+r)/2;
return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
}
} s, mxseg;
struct mnsegtree
{
int d[4*nx];
void build(int l, int r, int i)
{
d[i]=1e9;
if (l==r) return;
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
}
void update(int l, int r, int i, int idx, int vl)
{
if (idx<l||r<idx) return;
if (l==r) return d[i]=min(d[i], vl), void();
int md=(l+r)/2;
update(l ,md, 2*i, idx ,vl);
update(md+1, r, 2*i+1, idx, vl);
d[i]=min(d[2*i], d[2*i+1]);
}
int query(int l, int r, int i, int ql, int qr)
{
if (qr<l||r<ql) return 0;
if (ql<=l&&r<=qr) return d[i];
int md=(l+r)/2;
return min(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
}
} mnseg;
void dfs(int u, int p)
{
in[u]=++t;
//cout<<"update "<<u<<' '<<t<<' '<<rv[u]<<'\n';
if (u!=0) s.update(1, n, 1, t, rv[u]);
for (auto v:d[u]) dfs(v, u);
out[u]=t;
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
for (int i=0; i<N-1; i++) rv[S[0][i]]=i;
n=N, t=0, st=0, cnt=0;
int res=0;
for (int i=0; i<N; i++) in[i]=out[i]=0, d[i].clear();
for (int i=1; i<N; i++) d[F[i]].push_back(i);
s.build(1, N, 1);
mxseg.build(0, N-2, 1);
mnseg.build(0, N-2, 1);
for (int i=0; i<N-1; i++) mxseg.update(0, N-2, 1, i, i);
for (int i=0; i<N-1; i++) mnseg.update(0, N-2, 1, i, i);
for (int i=1; i<M; i++)
{
for (int j=0; j<N-1; j++)
{
mxseg.update(0, N-2, 1, rv[S[i][j]], j);
mnseg.update(0, N-2, 1, rv[S[i][j]], j);
}
}
dfs(0, 0);
while (st<N-1)
{
int mx=0;
for (int lst=st; lst<N-1; lst++)
{
mx=max(mx, s.query(1, n, 1, in[S[0][lst]], out[S[0][lst]]));
//cout<<"debug "<<st<<' '<<lst<<' '<<mx<<' '<<S[0][lst]<<'\n';
if (mxseg.query(0, N-2, 1, st, lst)>lst) continue;
if (mx==lst)
{
res++;
st=lst+1;
break;
}
}
}
return res;
}
