#include "september.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmax(a, b) a = max(a, b)
#define upmin(a, b) a = min(a, b)
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
vvll tree;
void dfs(ll node, ll papa, vll& dp) {
for (auto& nei : tree[node]) {
if (nei == papa) continue;
dfs(nei, node, dp);
upmax(dp[node], dp[nei]);
//upmax(dp[node], idx[nei]);
}
}
int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
ll n = N, m = M;
tree.clear();
tree.resize(n);
rep(i, 1, n) {
tree[i].push_back(F[i]);
tree[F[i]].push_back(i);
}
int ans = 0;
vvpll arr(m, vpll(n - 1));
rep(i, 0, m) {
vll dp(n);
rep(j, 0, n - 1) {
dp[S[i][j]] = j;
}
dfs(0, -1, dp);
rep(j, 0, n - 1) {
arr[i][j].first = dp[S[i][j]];
arr[i][j].second = S[i][j];
}
}
ll curEnd = 0;
multiset<ll> s;
map<ll, ll> cnt;
rep(i, 0, m) {
upmax(curEnd, arr[i][0].first);
cnt[arr[i][0].second]++;
s.insert(arr[i][0].second);
if (cnt[arr[i][0].second] == m) {
s.erase(arr[i][0].second); // Check if this erases all of the elements!!!
}
}
if (curEnd == 0 && s.empty()) ans++;
ll curPtr = 1;
while (curPtr < n - 1) {
rep(i, 0, m) {
upmax(curEnd, arr[i][curPtr].first);
cnt[arr[i][curPtr].second]++;
s.insert(arr[i][curPtr].second);
if (cnt[arr[i][curPtr].second] == m) {
s.erase(arr[i][curPtr].second); // Check if this erases all of the elements!!!
}
}
if (curPtr == curEnd && s.empty()) ans++;
curPtr++;
}
return ans;
}
/*
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
ll N, M;
cin >> N >> M;
vector<int> F(N);
F[0] = -1;
vector<vector<int>> S(M, vector<int>(N - 1));
rep(i, 1, N) cin >> F[i];
rep(i, 0, M) {
rep(j, 0, N - 1) {
cin >> S[i][j];
}
}
cout << solve(N, M, F, S) << endl;
}*/
/*
9 1
0 0 2 2 4 4 4 1
8 4 6 3 7 2 5 1
3 1
0 0
2 1
5 1
0 0 1 1
3 1 2 4
10 1
3 0 0 2 3 5 3 6 5
4 7 6 9 8 5 1 2 3
*/
