#include "september.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segTree{
int tree[400002];
void init(int i, int l, int r){
tree[i] = 0;
if(l==r) return;
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
}
void update(int i, int l, int r, int x, int v){
if(l==r){
tree[i] = v;
return;
}
int m = (l+r)>>1;
if(x<=m) update(i*2, l, m, x, v);
else update(i*2+1, m+1, r, x, v);
tree[i] = max(tree[i*2], tree[i*2+1]);
}
int query(int i, int l, int r, int v){ /// [1, i] 최댓값이 v보다 큰 인 최소 i 반환
if(tree[i] <= v) return -1;
if(l==r) return l;
int m = (l+r)>>1;
if(tree[i*2] > v) return query(i*2, l, m, v);
else return query(i*2+1, m+1, r, v);
}
} tree;
struct UnionFind{
int par[100002];
void init(int n){
for(int i=1; i<=n; i++) par[i] = i;
}
int find(int x){
if(x == par[x]) return x;
return x = find(par[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
if(x>y) swap(x, y);
par[y] = x;
}
} dsu[5];
struct Query{
int a, b;
Query(int a, int b): a(a), b(b){}
};
int n, m;
int par[100002];
vector<int> link[100002];
int arr[5][100002], ord[5][100002];
int DP[100002];
void dfs(int x){
for(int y: link[x]){
if(x) DP[y] = min(DP[y], DP[x]);
dfs(y);
}
}
int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
n = N, m = M;
for(int i=1; i<n; i++) par[i] = F[i], link[par[i]].push_back(i);
for(int i=0; i<m; i++) for(int j=1; j<N; j++){
arr[i][j] = S[i][j-1];
ord[i][arr[i][j]] = j;
}
vector<Query> queries;
/// Case 1
for(int d=0; d<m-1; d++){
tree.init(1, 1, n-1);
for(int i=1; i<n; i++){
int x = tree.query(1, 1, n-1, ord[d+1][arr[d][i]]);
if(x != -1) queries.push_back(Query(arr[d][x], arr[d][i]));
tree.update(1, 1, n-1, i, ord[d+1][arr[d][i]]);
}
}
/// Case 2
for(int d=0; d<m; d++){
for(int i=0; i<n; i++) DP[i] = ord[d][i];
dfs(0);
for(int i=0; i<n; i++){
if(DP[i] < ord[d][i]){
queries.push_back(Query(arr[d][DP[i]], i));
}
}
}
/// 본격 작업 시작
for(int d=0; d<m; d++) dsu[d].init(n-1);
while(!queries.empty()){
int A = queries.back().a, B = queries.back().b; queries.pop_back();
for(int d=0; d<m; d++){
int ad = dsu[d].find(ord[d][A]), bd = dsu[d].find(ord[d][B]);
if(ad > bd) swap(ad, bd);
while(ad != bd){
queries.push_back(Query(arr[d][bd-1], arr[d][bd]));
dsu[d].merge(bd-1, bd);
bd = dsu[d].find(bd);
}
}
}
int ans = 0;
for(int i=1; i<n; i++) if(dsu[0].find(i) == i) ans++;
/// 초기화
for(int i=0; i<=n; i++){
link[i].clear();
DP[i] = 0;
}
return ans;
}
