#include "september.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<int>>gp;
vector<int>ent,seg,v;
void update(int l,int r,int u,int x){
if(l==r && l==x){
seg[u]=1;
return;
}
int mid = (l+r)/2;
if(mid>=x) update(l,mid,u*2+1,x);
else update(mid+1,r,u*2+2,x);
seg[u]=seg[u*2+1]+seg[u*2+2];
}
int get(int l,int r,int u,int lx,int rx){
if(l>=lx && r<=rx) return seg[u];
if(l>rx || r<lx) return 0;
int mid = (l+r)/2;
return get(l,mid,u*2+1,lx,rx)+get(mid+1,r,u*2+2,lx,rx);
}
void dfs(int u,int p){
v.push_back(u);
for(int &i:gp[u]){
if(i!=p){
dfs(i,u);
ent[u]+=ent[i];
}
}
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
gp = vector<vector<int>>(N);
vector<int>sub(N,1);
v.clear();
for(int i = 1;i<N;i++){
gp[F[i]].push_back(i);
gp[i].push_back(F[i]);
}
int ans = 0;
ent = vector<int>(N,1);
dfs(0,-1);
vector<int>place(N),t(N),ok(N);
for(int i = 0;i<N;i++) place[v[i]]=i;
int s = 1;
set<int>st;
while(s<N) s*=2;
seg = vector<int>(2*s);
for(int k = 0;k+1<N;k++){
for(int i = 0;i<M;i++){
int u = S[i][k];
st.insert(u);
t[u]++;
update(0,s-1,0,place[u]);
}
while(st.size()){
int u = *st.rbegin();
if(t[u]!=M) break;
if(get(0,s-1,0,place[u],place[u]+ent[u]-1)==ent[u]){
st.erase(u);
}
else break;
}
if(st.empty()){
ans++;
}
}
return ans;
}
