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

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

const int kMaxN = 1e5 + 5, kMod = 998244353, kBase = 13331;

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

constexpr int qpow(int bs, int64_t idx = kMod - 2) {
  int ret = 1;
  for (; idx; idx >>= 1, bs = (int64_t)bs * bs % kMod)
    if (idx & 1)
      ret = (int64_t)ret * bs % kMod;
  return ret;
}

inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }

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;
}

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;
  std::vector<int> mul, sum;
  now.resize(m), mul.resize(m, 1), sum.resize(m, 0);
  for (int i = 0; i < n - 1; ++i) {
    for (int j = 0; j < m; ++j) {
      now[j].emplace_back(S[j][i]);
      mul[j] = 1ll * mul[j] * S[j][i] % kMod, inc(sum[j], S[j][i]);
    }
    bool fl = 1;
    for (int j = 0; j + 1 < m; ++j) fl &= (mul[j] == mul[j + 1] && sum[j] == sum[j + 1]);
    if (check(now)) ++ans;
  }
  return ans;
}