#include <iostream>
#include <vector>
#include <set>
using namespace std;
#include "september.h"
struct segTree{
int l; int r;
int sum;
segTree * lc;
segTree * rc;
segTree(int ind){
l = r = ind;
lc = rc = nullptr;
sum = 0;
}
segTree(segTree * le, segTree * ri){
lc = le; rc = ri;
sum = 0;
l = le->l; r = ri->r;
}
};
segTree* build(int l, int r){
int mid = (l+r)/2;
if(l == r) return new segTree(l);
else return new segTree(build(l, mid), build(mid+1, r));
}
int query(segTree * st){
if(st->r - st->l + 1 == st->sum) return 1;
if(st->lc->sum && (st->rc->sum!=(st->rc->r - st->rc->l + 1))) return 0;
if(!st->lc->sum) return query(st->rc);
else return query(st->lc);
}
void update(segTree * st, int ind){
if(st->l == st->r){
st->sum = 1;
return;
}
int mid = (st->l + st->r)/2;
if(ind<=mid) update(st->lc, ind);
else update(st->rc, ind);
st->sum = st->rc->sum + st->lc->sum;
return;
}
vector<vector<int>> adj;
vector<int> subtreeSize;
vector<int> subtreeSum;
set<int> picked;
void findSize(int st){
for(auto i : adj[st]) findSize(i);
int ans = 1;
for(auto i : adj[st]) ans += subtreeSize[i];
subtreeSize[st] = ans;
}
void dfs(int st){
for(auto i : adj[st]) dfs(i);
subtreeSum[st] = (picked.find(st) != picked.end());
for(auto i : adj[st]) subtreeSum[st] += subtreeSum[i];
}
int solve(int N, int M, vector<int> F, vector<vector<int>> S){
picked.clear();
adj.assign(N, {});
subtreeSize.assign(N, 0);
for(int i = 1; i<N; i++) adj[F[i]].push_back(i);
findSize(0);
segTree * sg = build(0, N-1);
int ans = 0;
for(int i = 0; i<N-1; i++){
for(int j = 0; j<M; j++){
picked.insert(S[j][i]);
update(sg, S[j][i]);
}
if(picked.size() == i+1){
ans += query(sg);
}
}
return ans;
}
