#include "september.h"
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> par;
int solve(int N, int M, vector<int> F, vector<std::vector<int>> S) {
n = N;
m = M;
par = F;
vector<int> early(n, n), late(n, 0);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n-1; j++) {
early[S[i][j]] = min(early[S[i][j]], j);
late[S[i][j]] = max(late[S[i][j]], j);
}
}
vector<int> maxR(n, 0);
for (int i = 1; i < n; i++) {
maxR[early[i]] = max(maxR[early[i]], late[i]);
}
vector<int> cnt(n, 0);
vector<bool> inside(n, false);
for (int i = 1; i < n; i++) cnt[par[i]]++;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int tot = 0;
set<int> proc;
int maxEnd = 0;
for (int i = 0; i < n - 1; i++) {
maxEnd = max(maxEnd, maxR[i]);
for (int j = 0; j < m; j++) {
proc.insert(S[j][i]);
}
if (maxEnd != i) continue;
for (auto x: proc) {
pq.push({cnt[x], x});
inside[x] = true;
while (!pq.empty()) {
if (cnt[pq.top().second] != pq.top().first) {
pq.pop();
continue;
}
int curr = pq.top().second;
if (cnt[curr] == 0) {
pq.pop();
cnt[par[curr]]--;
if (inside[par[curr]]) pq.push({cnt[par[curr]], par[curr]});
continue;
}
break;
}
}
if (pq.empty()) tot++;
proc.clear();
}
return tot;
}
