#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);
if (in[v] < pos[u]) continue;
in[u] = in[v];
int pu = fp(u), pv = fp(v);
if (pu != pv) par[pu] = pv;
}
}
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;
vector<int> mx(N, 0), mn(N, N);
for (int i = 1; i < N; i++) mx[fp(i)] = max(mx[fp(i)], in[i]);
for (int i = 1; i < N; i++) mn[fp(i)] = min(mn[fp(i)], pos[i]);
for (int i = 1; i < N; i++) mp[mn[fp(i)]]++, mp[mx[fp(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();
}
