#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// https://codeforces.com/blog/entry/79148
class Timer: chrono::high_resolution_clock {
const time_point start_time;
public:
Timer(): start_time(now()) {}
rep elapsed_time() const {
return chrono::duration_cast<chrono::milliseconds>(now() - start_time).count();
}
} timer;
int solve(int n, int m, vector<int> p, vector<vector<int>> s) {
vector<array<int, 2>> segs(n, {n, -1});
segs[0] = {-1, -1};
for (int i = 0; i < m; i++) {
vector<int> rev(n), cnt(n, 0);
for (int j = 0; j < n - 1; j++) {
rev[s[i][j]] = j;
segs[s[i][j]][0] = min(segs[s[i][j]][0], j);
segs[s[i][j]][1] = max(segs[s[i][j]][1], j);
}
for (int i = 1; i < n; i++) {
cnt[p[i]]++;
}
queue<int> q;
for (int i = 0; i < n; i++) {
if (!cnt[i]) {
q.push(i);
}
}
while (q.size()) {
int u = q.front();
q.pop();
if (!u) {
break;
}
segs[p[u]][1] = max(segs[p[u]][1], segs[u][1]);
cnt[p[u]]--;
if (!cnt[p[u]]) {
q.push(p[u]);
}
}
}
sort(segs.begin(), segs.end());
vector<int> ans(n - 1);
ans[0] = 1;
int pos = 1, cur = 1;
for (int i = 1; i < n; i++) {
if (pos > segs[i][1]) {
continue;
}
if (pos == segs[i][0]) {
cur++;
}
while (pos <= segs[i][1]) {
ans[pos] = cur;
pos++;
}
}
return ans[n - 2];
}
