#include "september.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int get(int v, vector<int>& parent) {
if (parent[v] == v) return v;
return parent[v] = get(parent[v], parent);
}
void union_set(int u, int v, vector <int>& parent) {
int pu = get(u, parent);
int pv = get(v, parent);
if (pu != pv) {
parent[pu] = pv;
}
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
vector <int> parent(N, 0);
for (int i = 0; i < N; i++) {
parent[i] = i;
}
for (int T = 0; T < M; T++) {
vector <int> p(N, 0);
vector <int> pos(N, 0);
for (int i = 0; i < N - 1; i++) {
pos[S[T][i]] = i;
p[i] = i;
}
vector <pair<int,int>> seg;
for (int i = 1; i < N; i++) {
if (F[i] == 0) continue;
if (pos[F[i]] < pos[i]) {
seg.push_back(make_pair(pos[F[i]], pos[i]));
}
}
sort(seg.begin(), seg.end());
int idx = -1;
for (auto to : seg) {
int l = to.first, r = to.second;
if (idx >= l) {
for (int i = idx + 1; i <= r; i++) p[i] = p[i - 1];
idx = r;
}
else {
for (int i = l + 1; i <= r; i++) p[i] = p[i - 1];
idx = r;
}
}
for (int i = 1; i < N - 1; i++) {
if (p[i] == p[i - 1]) {
union_set(S[T][i - 1], S[T][i], parent);
}
}
}
set <int> ans;
for (int i = 1; i < N; i++) {
ans.insert(get(i, parent));
}
return (int)ans.size();
}
