#include "september.h"
#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")
int solve(int n, int m, std::vector<int> f, std::vector<std::vector<int>> s) {
#define int int64_t
vector<int> id(n), sosal(n, -1);
for (int i = 0; i < n - 1; i++)
id[s[0][i]] = i;
for (int i = 1; i < n; i++) {
sosal[f[i]] = max(sosal[f[i]], id[i] + 1);
}
const int INF = 1e12;
vector<int> mxx(n);
for (int i = 0; i + 1 < n; i++)
mxx[i + 1] = sosal[s[0][i]];
for (int i = 1; i < n; i++)
mxx[i] = max(mxx[i], mxx[i - 1]);
mt19937 rnd(1488);
vector<int> hsh(n);
for (int i = 1; i < n; i++)
hsh[i] = rnd();
vector<int> ph1(n), penis(n);
for (int i = 0; i + 1 < n; i++) {
int cur_val = 0;
for (int j = 0; j < m; j++)
cur_val += hsh[s[j][i]];
ph1[i + 1] = cur_val + ph1[i];
cur_val = 0;
for (int j = 0; j < m; j++)
cur_val += hsh[s[0][i]];
penis[i + 1] = cur_val + penis[i];
}
vector<int> dp(n, -INF);
dp[0] = 0;
vector<int> fenw(n + 10, -INF);
auto upd = [&](int id, int x) {
id += 1;
for (; id < n + 10; id += id & -id)
fenw[id] = max(fenw[id], x);
};
auto get = [&](int r) -> int {
int res = -INF;
for (; r > 0; r -= r & -r)
res = max(res, fenw[r]);
return res;
};
upd(0, 0);
for (int i = 1; i < n; i++) {
if (ph1[i] != penis[i])
continue;
if (mxx[i] > i)
continue;
int val = get(i) + 1;
dp[i] = val;
upd(i, val);
// for (int j = 0; j < i; j++) {
// dp[i] = max(dp[i], dp[j] + 1);
// }
}
return dp[n - 1];
}
// int32_t main() {
// using namespace std;
// int t; cin >> t;
// int n, m; cin >> n >> m;
// vector<int32_t> f(n - 1);
// vector<vector<int32_t>> s(m, vector<int32_t>(n - 1));
// for (int32_t &i : f)
// cin >> i;
// for (auto &i : s)
// for (auto &j : i)
// cin >> j;
// cout << solve(n, m, f, s);
// }
