#include "september.h"
#include <bits/stdc++.h>
using namespace std;
int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
// 1. Pre-calculate out-degrees for nodes 1 to N-1.
// Node 0 is the root and is never shed, so we only care about
// children that are also part of the shedding process (1 to N-1).
vector<int> outDegree(N, 0);
for (int i = 1; i < N; ++i) {
if (F[i] != -1) {
outDegree[F[i]]++;
}
}
// 2. Track the state of the "shed" set V.
vector<int> seen_count(N, 0); // How many volunteers have seen this node
vector<int> child_cnt_in_V(N, 0); // How many children of this node are in V
int total_unique = 0; // Number of unique nodes in the current set V
long long current_outdegree_sum = 0; // Total children expected by nodes in V
long long current_parent_in_count = 0; // Total children in V whose parent is also in V
int days = 0;
// 3. Iterate through the recording sequence (length N-1)
for (int j = 0; j < N - 1; ++j) {
for (int m = 0; m < M; ++m) {
int u = S[m][j];
// If this is the first time ANY volunteer records this node
if (++seen_count[u] == 1) {
total_unique++;
current_outdegree_sum += outDegree[u];
// If u's parent is already in the shed set, update internal edge count
if (F[u] > 0 && seen_count[F[u]] > 0) {
current_parent_in_count++;
}
// If any of u's children were already added, update internal edge count
current_parent_in_count += child_cnt_in_V[u];
// Notify parent that this child is now in the shed set
if (F[u] != -1) {
child_cnt_in_V[F[u]]++;
}
}
}
// Condition for a valid day-end:
// 1. All M volunteers have recorded the same set of nodes (total_unique == j + 1)
// 2. For all nodes in the set, all their children are also in the set
// (current_outdegree_sum == current_parent_in_count)
if (total_unique == j + 1 && current_outdegree_sum == current_parent_in_count) {
days++;
}
}
return days;
}
