#include "september.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(X) X.begin(), X.end()
#define allr(X) X.rbegin(), X.rend()
using namespace std;
struct sgt{
vector<ll>st, lz;
sgt(ll n){st.assign(4 * n + 5, 0); lz.assign(4 * n + 5, 0);}
void lazy(ll l, ll r, ll v){
if(!lz[v]) return ;
st[v] = r - l + 1;
if(l != r){
lz[v << 1 | 1]=
lz[v << 1] = 1;
}
lz[v] = 0;
}
ll get(ll l, ll r, ll ql, ll qr, ll v){
lazy(l, r, v);
if(qr < l or ql > r) return 0;
if(ql <= l and r <= qr) return st[v];
ll mid = (l + r) / 2;
return get(l, mid, ql, qr, v << 1) + get(mid + 1, r, ql, qr, v << 1|1);
}
void upd(ll l, ll r, ll ql, ll qr, ll v){
lazy(l, r, v);
if(qr < l or ql > r) return ;
if(ql <= l and r <= qr){
lz[v] = 1;
lazy(l, r, v);
return ;
}
ll mid = (l + r) / 2;
upd(l, mid, ql, qr, v << 1);
upd(mid + 1, r, ql, qr, v << 1 | 1);
st[v] = st[v << 1] + st[v << 1 | 1];
}
};
ll timer = 0;
vector<vector<ll>>g;
vector<ll>tin, tout;
void dfs(ll u, ll p = -1){
tin[u] = ++timer;
for(ll &v : g[u]){
if(v == p) continue;
dfs(v, u);
}
tout[u] = timer;
}
int solve(int n, int m, vector<int> f, vector<vector<int>> s) {
sgt sg(n);
timer = 0;
g.assign(n, {});
tin.assign(n, -1);
tout.assign(n, -1);
for(ll i = 1; i < n; i++)
g[f[i]].pb(i),
g[i].pb(f[i]);
dfs(0);
vector<ll>cnt(n, 0), ccnt(n + 1, 0);
ll k = 0;
for(ll i = 0; i < n - 1; i++){
for(ll j = 0; j < m; j++){
ccnt[cnt[s[j][i]]++]--;
ccnt[cnt[s[j][i]]]++;
sg.upd(0, n, tin[s[j][i]], tout[s[j][i]], 1);
}
bool bl1 = (ccnt[m] == i + 1);
bool bl2 = (sg.get(0, n, 0, n, 1) == i + 1);
k += (bl1 & bl2);
}
return k;
}
