#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;
struct IT{
int n;
vi T;
IT () {};
IT(int _n){
int k = 1;
n = _n;
while (2 * k <= n) k *= 2;
T.resize(4 * k, 0);
}
void update(int id, int l, int r, int pos, int val){
if(l == r){
T[id] = val;
return;
}
int m = (l + r)/2;
if (pos <= m) update(id*2, l, m, pos, val);
else update(id*2+1, m+1, r, pos, val);
T[id] = max(T[id*2], T[id*2+1]);
}
int get(int id, int l, int r, int u, int v){
if (l > v || r < u) return 0;
if (u <= l && r <= v) return T[id];
int m = (l + r)/2;
return max(get(id*2, l, m, u, v), get(id*2+1, m+1, r, u, v));
}
};
mt19937 rd(time(0));
int Rand(int l, int r){
return l + (rd()%(r - l + 1) + r - l + 1) %(r - l + 1);
}
int n, m, in[N], ou[N], v[N], timer;
vi G[N];
void dfs(int u, int par){
in[u] = ++timer;
for (int &v : G[u]){
if (v == par) continue;
dfs(v, u);
}
ou[u] = timer;
}
int solve(int _n, int _m, vi F, vector<vi> S){
n = _n; m = _m;
FOR (i, 1, n - 1){
G[i].pb(F[i]);
G[F[i]].pb(i);
}
dfs(0, -1);
vector<IT> seg(m);
FOR (i, 0, m- 1){
seg[i] = IT(n);
FOR (j, 0, n - 2){
seg[i].update(1, 1, n, in[S[i][j]], j);
}
}
int last = -1;
vector<ii> a;
FOR (j, 0, n - 2){
int mx = 0;
FOR (i, 0, m - 1){
mx = max(mx, seg[i].get(1, 1, n, in[S[i][j]], ou[S[i][j]]));
}
if (last < j){
a.pb({j, mx});
} else {
a.back().se = max(a.back().se, mx);
}
last = a.back().se;
}
FOR (i, 1, n - 1) v[i] = Rand(1, 1e9);
vector<vi> pref(m, vi(n, 0));
FOR (i, 0, m - 1){
pref[i][0] = v[S[i][0]];
FOR (j, 1, n - 2){
pref[i][j] = pref[i][j-1] + v[S[i][j]];
}
}
vector<int> dp(n + 2, 0);
dp[0] = 0;
assert(!a.empty());
FOR (i, 1, (int)a.size()){
vector<int> sum(m, 0);
FORD(j, i, 1){
FOR (z, 0, m - 1) sum[z] += pref[z][a[j-1].se] - pref[z][a[j-1].fi] + v[S[z][a[j-1].fi]];
int ok = 1;
FOR (z, 0, m - 2) if (sum[z] != sum[z+1]) ok = 0;
if (ok) dp[i] = max(dp[i], dp[j-1] + 1);
}
}
FOR (i, 0, n - 1){
G[i].clear();
in[i] = ou[i] = 0;
}
timer = 0 ;
return dp[a.size()];
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
//cout << solve(5, 2, {-1, 0, 0,1, 1}, {{1, 2, 3, 4}, {4, 1, 2, 3}}) << '\n';
cout << solve(3, 1, {-1, 0, 0}, {{1, 2}});
return 0;
}
