#include <bits/stdc++.h>
#include "september.h"
using namespace std;
#ifdef LOCAL
#include "deb.h"
#else
#define debug(...)
#endif
int solve(int n, int m, vector<int> f, vector<vector<int>> s) {
mt19937_64 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
int ans = 0;
vector<vector<int>> g(n);
for (int i = 1; i < n; i++) {
g[f[i]].push_back(i);
}
vector<set<int>> sts(m);
vector<int> violate(m);
vector<long long> hashes(m);
vector<long long> weights(n);
for (int i = 0; i < n; i++) {
weights[i] = rng() % 10000000;
}
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m; j++) {
for (int who : g[s[j][i]]) {
if (sts[j].find(who) == sts[j].end()) {
violate[j]++;
}
}
if (sts[j].find(f[s[j][i]]) != sts[j].end()) {
violate[j]--;
}
sts[j].insert(s[j][i]);
}
bool ok = true;
for (int j = 0; j < m; j++) {
if (violate[j] != 0) {
ok = false;
}
}
for (int j = 0; j < m; j++) {
hashes[j] += (long long) (s[j][i] + 1) * weights[s[j][i]];
}
for (int j = 0; j < m; j++) {
if (hashes[j] != hashes[0]) {
ok = false;
}
}
ans += ok;
}
return ans;
}
