#include "september.h"
#include <bits/stdc++.h>
#include <vector>
#ifndef DEVAL
#include "stub.cpp"
#endif
using namespace std;
#define pii pair<int , int>
#define A first
#define B second
bool vis[(int)1e5+1];
int far[(int)1e5+1];
int idx[5][(int)1e5+1];
vector<vector<int>> adj;
vector<vector<int>> graph ;
vector<vector<int>> subtree;
struct SegmentTree{
vector<int> seg;
int m;
void init(int n){
m = 1<<(__lg(n-1)+1);
seg.clear();
seg.resize(2*m);
}
void add(int id , int val , int s , int e , int p){
if (s == e) {seg[p] += val; return;}
if (id <= (s+e)/2) add(id , val , s , (s+e)/2 , 2*p);
else add(id , val , (s+e)/2 + 1 , e , 2*p+1);
seg[p] = seg[2*p] + seg[2*p+1] ;
}
int get_sum(int l , int r , int s , int e , int p){
if (l > e || r < s) return 0;
else if (l <= s && r >=e ) return seg[p];
return get_sum(l , r ,s , (s+e)/2 , 2*p) + get_sum(l , r , (s+e)/2 + 1 , e , 2*p+1);
}
void add(int id , int val){
add(id , val ,1 , m, 1);
}
int get_sum(int l , int r){
return get_sum(l , r , 1, m , 1) ;
}
};
SegmentTree st;
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
adj.clear(); adj.resize(N);
st.init(N);
for (int i = 1 ; i < N ; i++){
adj[F[i]].push_back(i);
}
int freq[N+1] = {};
int o = 0 , c = 0;
set<int> C;
int ans = 0;
for (int i = 0 ; i < N-1 ; i++){
bool f = 1;
for (int j = 0 ; j < M ; j++){
if (freq[S[j][i]] == 0) o++;
freq[S[j][i]]++;
if (freq[S[j][i]] == M) {
c++; C.insert(S[j][i]);
if (C.find(F[S[j][i]]) != C.end()) st.add(F[S[j][i]] , 1);
for (auto k : adj[S[j][i]]) if (C.find(k) == C.end()) st.add(S[j][i] , -1);
}
}
if (o == c && st.get_sum(1 , N-1) == 0) ans++;
}
return ans;
}