#include "september.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define tiii tuple<int,int,int>
#define tiiii tuple<int,int,int,int>
#define pb push_back
#define eb emplace_back
#define emp emplace
#define mkp make_pair
#define mkt make_tuple
#define vctr vector
#define arr array
#define all(x) x.begin(), x.end()
#define amin(a,b) a = min(a,b)
#define amax(a,b) a = max(a,b)
#define brick(x) cout << #x << " = " << (x) << " | "
#define dbg(x) cout << #x << " = " << (x) << '\n'
#define vdbg(a) cout << #a << " = "; for(auto _x : a)cout << _x << ' '; cout << '\n'
#define adbg(a,n) cout << #a << " = "; for(int _i = 1; _i <= n; ++_i)cout << a[_i] << ' '; cout << '\n'
#define adbg0(a,n) cout << #a << " = "; for(int _i = 0; _i < n; ++_i)cout << a[_i] << ' '; cout << '\n'
mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));
int uid(int a, int b) { return uniform_int_distribution<int>(a,b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a,b)(rng); }
const int MOD = 1e9+7; // 998244353;
ll h[100005];
int dp[5][100005];
vctr<int> adj[100005];
int dp2[100005];
int m;
void dfs(int node) {
for (auto it : adj[node]) {
dfs(it);
for (int i = 0; i < m; ++i) {
amax(dp[i][node],dp[i][it]);
}
}
return;
}
int solve(int n, int _m, vctr<int> vf, vctr<vctr<int>> vs) {
m = _m;
for (int i = 0; i < n; ++i) {
adj[i].clear();
}
for (int i = 1; i <= n-1; ++i) {
h[i] = rng();
adj[vf[i]].pb(i);
// brick(vf[i]);dbg(i);
}
for (int j = 0; j < m; ++j) {
for (int i = 0; i < n-1; ++i) {
dp[j][vs[j][i]] = i;
}
}
// adbg(dp[0],n-1);
dfs(0);
// adbg(dp[0],n-1);
for (int i = 0; i < n-1; ++i) {
dp2[i] = 0;
for (int j = 0; j < m; ++j) {
amax(dp2[i],dp[j][vs[j][i]]);
// dbg(dp[j][vs[j][i]]);
}
if (i)amax(dp2[i],dp2[i-1]);
};
// adbg0(dp2,n);
ll cur[5] = {0,0,0,0,0};
int ans = 0;
for (int i = 0; i < n-1; ++i) {
for (int j = 0; j < m; ++j) {
cur[j] ^= h[vs[j][i]];
}
bool check = dp2[i] == i;
for (int j = 0; j+1 < m; ++j) {
if (cur[j] != cur[j+1])check = false;
}
// brick(i);dbg(check);
ans += check;
}
return ans;
}
