#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
const long long mod=1e9+9;
int n,m,bad,ans;
int parent[MAXN],deg[MAXN];
long long hesh[10],power[MAXN];
bool in[MAXN];
void reset_hesh(){
for(int i=0;i<m;i++)hesh[i]=0;
}
int solve(int N, int M, vector<int> F,vector< vector<int> > S){
n=N; m=M; ans=0;
for(int i=0;i<n;i++)deg[i]=0;
reset_hesh();
for(int i=0;i<n;i++){
parent[i]=F[i];
if(parent[i]!=-1)deg[parent[i]]++;
}
power[0]=1;
for(int i=1;i<n;i++)power[i]=(power[i-1]*2)%mod;
for(int i=0;i<n-1;i++){
for(int f=0;f<m;f++){
if(f==0){
deg[parent[S[f][i]]]--;
if(in[parent[S[f][i]]])bad--;
in[S[f][i]]=true;
bad+=deg[S[f][i]];
}
hesh[f]+=power[S[f][i]];
}
for(int f=0;f<m;f++){
if(f<m-1 and hesh[f]!=hesh[f+1])break;
if(f==m-1 and bad==0){
ans++; reset_hesh();
}
}
}
return ans;
}
/*int main(){
cout<<solve(3, 1, {-1, 0, 0}, {{1, 2}})<<"\n";
cout<<solve(5, 2, {-1, 0, 0, 1, 1}, {{1, 2, 3, 4}, {4, 1, 2, 3}})<<"\n";
return 0;
}*/
