#include "september.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'
// #include "stub.cpp"
using lint = __int128;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rnd(l, r) uniform_int_distribution<lint>(l, r)(rng)
int solve(int n, int m, std::vector<int> f, std::vector<std::vector<int>> s) {
vector<vector<int>> adj(n);
vector<int> a(n);
for(int i = 1; i < n; i++) {
adj[f[i]].pb(i);
a[i] = rnd(1e18, 1e25);
}
vector<int> tin(n), tout(n);
int timer = 0;
auto dfs = [&](auto &&self, int v) -> void {
tin[v] = ++timer;
for(auto to : adj[v]) {
self(self, to);
}
tout[v] = timer;
};
dfs(dfs, 0);
set<pair<int, int>> st;
for(int i = 1; i < n; i++) {
st.emplace(tin[i], i);
// cout << i << ": " << tin[i] << ' ' << tout[i] << nl;
}
vector<int> mx(n);
for(int i = 0; i < m; i++) {
for(int j = 0; j < n - 1; j++) {
int v = s[i][j];
mx[v] = max(mx[v], j);
}
}
int j = 0, k = 0;
vector<lint> sum(m);
map<lint, int> mp;
auto update = [&](int i, lint x) {
if(--mp[sum[i]] <= 0) mp.erase(sum[i]);
sum[i] += x;
mp[sum[i]]++;
};
auto update2 = [&](int u) {
vector<int> del;
for(auto it = st.lower_bound({tin[u], 0}); it != st.end(); it++) {
int v = it -> second;
if(!(tin[v] >= tin[u] && tout[v] <= tout[u])) break;
k = max(k, mx[v]);
del.pb(v);
}
// cout << "Deleted: ";
for(auto &x : del) {
// cout << x << ' ';
st.erase({tin[x], x});
}
// cout << nl;
};
auto add = [&]() {
for(int i = 0; i < m; i++) {
// update(i, a[s[i][j]]);
update2(s[i][j]);
}
j++;
};
int ans = 0;
while(j < n - 1) {
// cout << nl << ans + 1 << ": " << nl;
do {
add();
} while(j <= k);
// cout << j + 1 << ' ' << k + 1 << nl;
// mp.clear();
// k = 0;
// cout << nl;
ans++;
}
return ans;
}
