#include "september.h"
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
int64_t Rand(int64_t l, int64_t h) {
return uniform_int_distribution<int64_t>(l, h)(rng);
}
int64_t H[maxn];
int64_t P[5][maxn];
int64_t G[5];
int doable[maxn], sz[maxn];
vector<int> adj[maxn];
int head[maxn], heavy[maxn], pos[maxn], id = 0;
void pfs(int u) {
sz[u] = 1; int mxsz = -1;
for (int v : adj[u]) {
pfs(v);
sz[u] += sz[v];
if (mxsz < sz[v]) {
mxsz = sz[v];
heavy[u] = v;
}
}
}
void dcp(int u, int p) {
head[u] = p; pos[u] = ++id;
if (heavy[u]) dcp(heavy[u], p);
for (int v : adj[u])
if (v != heavy[u]) dcp(v, v);
}
int st[4*maxn], lz[4*maxn];
void down(int r) {
if (lz[r]) {
st[r<<1] += lz[r];
st[r<<1|1] += lz[r];
lz[r<<1] += lz[r];
lz[r<<1|1] += lz[r];
lz[r] = 0;
}
}
void update(int u, int v, int d, int r = 1, int lo = 1, int hi = n) {
if (u <= lo && hi <= v) {
st[r] += d;
lz[r] += d;
return;
}
down(r);
int mid = (lo + hi) >> 1;
if (u <= mid) update(u, v, d, r<<1, lo, mid);
if (v > mid) update(u, v, d, r<<1|1, mid+1, hi);
st[r] = min(st[r<<1], st[r<<1|1]);
}
int solve(int N, int M, vector<int> F, vector<vector<int> > S) {
n = N;
for (int i = 0; i < N; i++) ++F[i];
for (int i = 0; i < M; i++) {
S[i].insert(S[i].begin(), 0);
for (int j = 1; j < N; j++) ++S[i][j];
}
id = 0;
for (int i = 1; i <= 4*N; i++) st[i] = lz[i] = 0;
for (int i = 1; i <= N; i++) H[i] = Rand(0, LLONG_MAX);
for (int i = 0; i < M; i++)
for (int j = 1; j < N; j++) P[i][j] = (P[i][j-1] ^ H[S[i][j]]);
int ans = 0, last = 1;
for (int i = 1; i <= N; i++) heavy[i] = 0;
for (int i = 1; i < N; i++) adj[F[i]].emplace_back(i+1);
pfs(1);
dcp(1, 1);
for (int i = 1; i <= N; i++) --sz[i];
for (int i = 1; i <= N; i++) doable[i] = 0;
for (int i = 1; i < N; i++) {
int u = S[0][i];
// cerr << u << ' ';
update(pos[u], pos[u], -sz[u]);
u = F[u-1];
if (u) {
while (head[u] != head[1]) {
update(pos[head[u]], pos[u], 1);
u = F[head[u]-1];
}
update(pos[head[u]], pos[u], 1);
}
// cerr << st[1] << "\n";
doable[i] = (st[1] >= 0);
}
while (last < N) {
for (int o = last; o < N; o++) {
if (!doable[o]) continue;
for (int i = 0; i < M; i++) G[i] = (P[i][o]^P[i][last-1]);
if (1) {
int c = 1;
for (int i = 1; i < M; i++) if (G[i] != G[i-1]) {c = 0; break;}
if (c == 0) continue;
}
last = o+1;
break;
}
++ans;
}
for (int i = 1; i <= N; i++) adj[i].clear();
return ans;
}
/*
1
10 1
0 1 2 0 3 0 5 4 8
9 7 6 8 4 5 3 2 1
*/
