#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);
set<int> t;
vector<int> mx(N, 0), mn(N, N);
for (int i = 1; i < N; i++) {
mx[fp(i)] = max(mx[fp(i)], in[i]);
mn[fp(i)] = min(mn[fp(i)], pos[i]);
t.emplace(fp(i));
}
vector<tuple<int, int, int>> a;
for (auto &x : t) a.emplace_back(mn[x], mx[x], x);
sort(a.begin(), a.end());
int prev = -1, idx = 0;
for (int i = 0; i < a.size(); 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();
}
