#include "september.h"
#include <bits/stdc++.h>

#ifdef ORZXKR
#include "stub.cpp"
#endif

const int kMaxN = 1e5 + 5;

int n, m, cnt;
int p[kMaxN], dfn[kMaxN], sz[kMaxN];
bool del[kMaxN];
std::vector<int> G[kMaxN];

void dfs(int u) {
  dfn[u] = ++cnt, sz[u] = 1;
  for (auto v : G[u]) {
    dfs(v);
    sz[u] += sz[v];
  }
}

bool check(std::vector<int> &vec) {
  static int cnt[kMaxN];
  std::fill_n(cnt + 1, n, 0);
  for (auto x : vec) ++cnt[dfn[x]];
  for (int i = 1; i <= n; ++i) cnt[i] += cnt[i - 1];
  for (auto x : vec) {
    assert(sz[x]);
    if (cnt[dfn[x] + sz[x] - 1] - cnt[dfn[x] - 1] != sz[x])
      return 0;
  }
  return 1;
}

bool check(std::vector<std::vector<int>> &vec) {
  for (auto &v : vec) {
    if (!check(v)) return 0;
  }
  return 1;
}

bool equal(std::vector<int> v1, std::vector<int> v2) {
  if (v1.size() != v2.size()) return 0;
  std::sort(v1.begin(), v1.end());
  std::sort(v2.begin(), v2.end());
  for (int i = 0; i < (int)v1.size(); ++i)
    if (v1[i] != v2[i])
      return 0;
  return 1;
}

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
  ::n = N, ::m = M, cnt = 0;
  for (int i = 1; i <= n; ++i) G[i].clear();
  for (int i = 1; i <= n; ++i) {
    p[i] = F[i - 1] + 1;
    if (p[i]) G[p[i]].emplace_back(i);
  }
  dfs(1);
  for (auto &vec : S) {
    for (auto &x : vec) ++x;
  }
  std::fill_n(del + 1, n, 0);
  int ans = 0;
  std::vector<std::vector<int>> now;
  now.resize(m);
  for (int i = 0; i < n - 1; ++i) {
    for (int j = 0; j < m; ++j) {
      now[j].emplace_back(S[j][i]);
    }
    bool fl = 1;
    for (int j = 0; j + 1 < m; ++j) fl &= equal(now[j], now[j + 1]);
    if (fl && check(now)) ++ans;
  }
  return ans;
}