#include "september.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int dfs(int node, vector<vector<int>> &down, vector<bool> &vis) {
int res = 0;
for (const auto &child : down[node]) {
if (!vis[child]) {
vis[child] = true;
res++;
res += dfs(child, down, vis);
}
}
return res;
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
int ans = 0;
vector<vector<int>> down(N, vector<int>());
for (int i = 1; i < N; i++) down[F[i]].push_back(i);
// "compress" the M queries
vector<int> comp(N, -1);
for (int m = 0; m < M; m++) {
for (int j = 0; j < N - 1; j++) {
comp[S[m][j]] = max(comp[S[m][j]], j);
}
}
int dels = 0;
int sweep = 0;
vector<bool> vis(N, false);
vector<int> cnt(N, 0);
for (int i = 0; i < N - 1; i++) {
// delete itself and all its children
// not including vis'd
if (!vis[comp[i]]) {
vis[comp[i]] = true;
dels++;
dels += dfs(comp[i], down, vis);
}
cerr << dels << endl;
// increment how many times we've seen this node
cnt[comp[i]]++;
// interval start and end
// first time we've seen it
if (cnt[comp[i]] == 1) sweep++;
// last time we've seen it
if (cnt[comp[i]] == M) sweep--;
// when an interval "closes," increment ans
// an interval closes when
// we've seen all the nodes in the interval
// specifically, for any node, it's subtree is contained in the interval
// thus, this is only possible when the amount of deletions
// is equal to the amount of nodes in the interval
if (i + 1 == dels && sweep == 0) {
ans++;
}
}
return ans;
}
