#include<bits/stdc++.h>
#include "september.h"
#include <vector>
#define pu push_back
#define po pop_back
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
int pos[5][100005], L, R, ans;
bool vis[100005];
vector<int> adj[100005];
set<int> s, t;
set<pii> u[5];
vector<pii> buang[5];
void dfs(int x){
if(vis[x]) return;
vis[x] = true;
t.insert(x);
for(auto i : adj[x]) dfs(i);
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++) pos[j][i] = 0;
vis[i] = false;
adj[i].clear();
}
s.clear(); t.clear();
for(int j = 0; j < M; j++) u[j].clear();
for(int i = 1; i < N; i++) adj[F[i]].pu(i);
for(int i = 0; i < N - 1; i++){
for(int j = 0; j < M; j++){
pos[j][S[j][i]] = i;
u[j].insert({i, S[j][i]});
}
}
L = ans = 0;
N--;
while(L < N){
for(int j = 0; j < M; j++) s.insert(S[j][L]);
while(!s.empty()){
t.clear();
for(auto i : s) dfs(i);
R = L;
for(auto i : t){
for(int j = 0; j < M; j++) R = max(R, pos[j][i]);
}
L = max(L, R);
s.clear();
for(int j = 0; j < M; j++) buang[j].clear();
for(int j = 0; j < M; j++){
for(auto i : u[j]){
if(i.fi > R) break;
if(vis[i.se]) buang[j].pu(i);
else s.insert(i.se);
}
}
for(int j = 0; j < M; j++){
for(auto i : buang[j]) u[j].erase(i);
}
}
L++;
ans++;
}
return ans;
}
