#pragma GCC optimize("O2,unroll-loops")
#include "september.h"
#include <string>
#include <cstdio>
#include <array>
#include <vector>
#include <algorithm>
struct max_segtree { std::vector<int> st; int n; max_segtree(int n) : st(n * 2), n(n) {} void pul(int i) { st[i] = std::max(st[i << 1], st[i << 1 | 1]); } int query(int l, int r) { int z = 0; for (l += n, r += n + 1; l < r; l /= 2, r /= 2) { if (l & 1) z = std::max(z, st[l++]); if (r & 1) z = std::max(st[--r], z); } return z; } void assign(int p, int k) { for (st[p += n] = k; p /= 2; ) pul(p); } };
const int NN = 100000;
const int MM = 5;
std::vector<int> g[NN];
int M, tin[NN], tout[NN], timer, pos[MM][NN];
using Lena = std::array<int, 5>;
void add_(Lena &a, const Lena &b) {
int i;
for (i = 0; i < M; ++i)
a[i] = std::max(a[i], b[i]);
}
Lena add(Lena a, const Lena &b) {
add_(a, b);
return a;
}
void dfs(int u) {
tin[u] = timer++;
for (auto v : g[u])
dfs(v);
tout[u] = timer - 1;
}
struct lena_segtree {
std::vector<Lena> st;
int n;
lena_segtree(int n) : st(n * 2), n(n) {}
void pul(int i) { st[i] = add(st[i << 1], st[i << 1 | 1]); }
Lena query(int l, int r) { Lena z {}; for (l += n, r += n + 1; l < r; l /= 2, r /= 2) { if (l & 1) add_(z, st[l++]); if (r & 1) add_(z, st[--r]); } return z; }
void update(int p, int q, int k) { p += n; st[p][q] = std::max(st[p][q], k); for (; p /= 2; ) pul(p); }
void update2(int p, const Lena &x) { add_(st[p += n], x); for (; p /= 2; ) pul(p); }
};
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
int i, j;
::M = M;
for (i = 0; i < N; ++i)
g[i].clear();
timer = 0;
if (M == 1) { auto S0 = S[0]; std::vector<int> pos(N); for (i = 0; i < N - 1; ++i) pos[S0[i]] = i; for (i = 1; i < N; ++i) g[F[i]].push_back(i); dfs(0); max_segtree ta(N), tb(N); for (i = 1; i < N; ++i) ta.assign(tin[i], pos[i]); for (i = N - 2; i >= 0; --i) { int u, last; u = S0[i]; last = ta.query(tin[u], tout[u]); last = std::max(last, tb.query(i, last)); tb.assign(i, last); } int K = 0; for (i = 0; i < N - 1;) { int until; until = tb.query(i, i); i = until + 1; ++K; } return K; }
for (i = 0; i < M; ++i)
for (j = 0; j < N - 1; ++j)
pos[i][S[i][j]] = j;
for (i = 1; i < N; ++i)
g[F[i]].push_back(i);
dfs(0);
std::vector<lena_segtree> tb;
std::vector<Lena> tc(N);
lena_segtree ta(N);
auto Put = [&](int u, Lena x) {
add_(x, tc[u]);
for (int j = 0; j < M; ++j)
add_(x, tb[j].query(0, x[j]));
for (int j = 0; j < M; ++j)
tb[j].update2(pos[j][u], x);
ta.update2(tin[u], x);
add_(tc[u], x);
};
for (i = 0; i < M; ++i)
tb.emplace_back(N);
for (i = 0; i < M; ++i)
for (j = 1; j < N; ++j)
ta.update(tin[j], i, pos[i][j]);
int is_line_graph = 1;
for (int i = 1; i < N; ++i)
is_line_graph &= F[i] == i - 1;
if (not is_line_graph) {
int what = 3;
if (N >= 2001)
what = 1;
for (i = 0; i < what; ++i) {
for (j = 0; j < N - 1; ++j) {
int u = S[i][j];
Put(u, ta.query(tin[u], tout[u]));
}
}
}
for (i = 1; i < N; ++i)
Put(i, ta.query(tin[i], tout[i]));
Lena at {};
int K = 0;
while (1) {
for (j = 0; j < M; ++j)
if (at[j] >= N - 1)
return K;
for (j = 0; j < M; ++j)
add_(at, tc[S[j][at[j]]]);
for (j = 0; j < M; ++j)
++at[j];
++K;
}
}
