#include "september.h"
#include <bits/stdc++.h>
using namespace std;
const int n = (int)1e5 + 1;
int par[n], pos[n], in[n];
vector<int> adj[n];
int fp(int x) {
if (par[x] == -1) return x;
return par[x] = fp(par[x]);
}
void dfs(int u) {
for (auto &v : adj[u]) {
dfs(v);
in[u] = max(in[u], in[v]);
}
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
for (int i = 0; i < N; i++) par[i] = -1, adj[i].clear();
for (int i = 1; i < N; i++) adj[F[i]].emplace_back(i);
for (auto &A : S) {
for (int i = 0; i < N-1; i++) pos[A[i]] = in[A[i]] = i;
for (auto &u : adj[0]) dfs(u);
vector<tuple<int, int, int>> a;
for (int i = 1; i < N; i++) a.emplace_back(pos[i], in[i], i);
sort(a.begin(), a.end());
int prev = -1, idx = 0;
for (int i = 0; i < N-1; i++) {
auto &[l, r, id] = a[i];
if (prev >= l) {
int pu = fp(idx), pv = fp(id);
if (pu != pv) par[pu] = pv;
}
if (prev <= r) prev = r, idx = id;
}
}
set<int> s;
for (int i = 1; i < N; i++) s.emplace(fp(i));
return (int)s.size();
}
