#include "september.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MXN=1e5+7;
vector<int> g[MXN];
int cnt=1,to_idx[MXN],r_idx[MXN],tree[MXN];
long long Xor[5];
long long to_hash[MXN];
void dfs(int u){
to_idx[u]=cnt++;
for(auto v:g[u]){
dfs(v);
}
r_idx[u]=cnt-1;
}
void update(int idx,int val){
for(int i=idx;i<MXN;i+=i&-i)tree[i]+=val;
}
int query(int idx){
int sum=0;
for(int i=idx;i>0;i-=i&-i)sum+=tree[i];
return sum;
}
int query(int l,int r){
if(l>r)return 0;
return query(r)-query(l-1);
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
int ans=0;
cnt=1;
for(int i=1;i<N;i++)g[F[i]].emplace_back(i);
for(int i=2;i<=N;i++)update(i,1);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
for(int i=1;i<N;i++)to_hash[i]=rng();
dfs(0);
int l=-1,nl=-1;
for(int j=0;j<N-1;j++){
for(int i=0;i<M;i++){
Xor[i]^=to_hash[S[i][j]];
}
bool good=1;
for(int i=0;i<M-1;i++){
if(Xor[i]!=Xor[i+1]){
good=0;
break;
}
}
if(good){
for(int k=nl+1;k<=j;k++){
update(to_idx[S[0][k]],-1);
}
nl=j;
bool done=1;
for(int k=l+1;k<=j;k++){
if(query(to_idx[S[0][k]]+1,r_idx[S[0][k]])!=0){
done=0;
break;
}
}
if(done){
ans++;
l=j;
}
}
}
for(int i=0;i<N-1;i++)g[i].clear();
for(int i=1;i<MXN;i++)tree[i]=0;
for(int i=0;i<M;i++)Xor[i]=0;
return ans;
}
