#include "september.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
vector<int> deg(N, 0);
for (int i = 1; i < N; i++) {
deg[i]++;
deg[F[i]]++;
}
for (int i = 1; i < N; i++)
deg[i]--;
auto is_valid = [&](vector<int> vec) {
unordered_set<int> s;
vector<int> Deg = deg;
for (int node : vec) {
if (Deg[node] == 0) {
while (1) {
if (node == 0) break;
Deg[F[node]]--;
if (Deg[F[node]] == 0) {
if (s.count(F[node])) {
s.erase(F[node]);
} else {
break;
}
}
node = F[node];
}
} else {
s.insert(node);
}
}
if (s.empty()) {
deg = Deg;
}
return s.empty();
};
int ans = 0;
vector<unordered_set<int>> vec(M);
for (int i = 0; i < N - 1; i++) {
for (int j = 0; j < M; j++)
vec[j].insert(S[j][i]);
bool ok = true;
for (int j = 1; j < M; j++)
if (vec[j] != vec[j - 1])
ok = false;
if (!ok) continue;
vector<int> to_check;
for (int node : vec[0])
to_check.push_back(node);
if (is_valid(to_check)) {
for (int j = 0; j < M; j++)
vec[j].clear();
ans += 1;
}
}
return ans;
}
