#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);
int prev = -1, cnt = 0;
map<int, int> mp;
for (int i = 1; i < N; i++) mp[pos[i]]++, mp[in[i]]--;
for (auto &[x, y] : mp) {
cnt += y;
if (cnt == 0) { prev = -1; continue; }
if (prev != -1) {
int pu = fp(A[prev]), pv = fp(A[x]);
if (pu != pv) par[pu] = pv;
} else prev = x;
}
}
set<int> s;
for (int i = 1; i < N; i++) s.emplace(fp(i));
return (int)s.size();
}
