#include "september.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
const ll mod = 1000000007;
const ll N = 100001;
int a[N+2], dp[N+2], dep[N+2], sub[N+2], id[N+2], ord[N+2], near[N+2];
vector<int> adj[N+2], order;
struct Segtree{
vector<int> t;
int off = 1;
Segtree(int n){
while(off < n)off <<= 1;
t.resize(2 * off, 0);
};
void update(int u, int v, int tp){
t[u += off] = v;
if(!tp)while(u >>= 1)t[u] = t[u * 2] + t[u * 2 + 1];
else while(u >>= 1)t[u] = max(t[u * 2], t[u * 2 + 1]);
}
int query(int n, int ql, int qh, int nl, int nh, int tp){
if(ql <= nl && nh <= qh)return t[n];
if(nl > qh || ql > nh)return 0;
int m = (nl + nh) / 2;
if(!tp)return query(n * 2, ql, qh, nl, m, tp) + query(n * 2 + 1, ql, qh, m + 1, nh, tp);
else return max(query(n * 2, ql, qh, nl, m, tp), query(n * 2 + 1, ql, qh, m + 1, nh, tp));
}
};
void dfs(int u, int par, int d){
dep[u] = d;
sub[u] = 1;
ord[u] = order.size();
order.pb(u);
for(auto &v : adj[u]){
if(v == par)continue;
dfs(v, u, d + 1);
sub[u] += sub[v];
}
}
int solve(int n, int m, std::vector<int> f, std::vector<std::vector<int>> s){
for(int i = 1; i < n; i++){
adj[f[i]].pb(i);
adj[i].pb(f[i]);
}
dfs(0, 0, 0);
vector<Segtree> segtree(m, Segtree(n));
Segtree mid(n);
for(int j = 0; j < m; j++){
for(int i = 0; i < n - 1; i++){
id[s[j][i]] = max(id[s[j][i]], i);
}
}
stack<int> st;
for(int i = n - 1; i >= 0; i--){
while(!st.empty() && dep[order[st.top()]] > dep[order[i]])st.pop();
if(st.empty())near[i] = i;
else near[i] = st.top() - 1;
st.push(i);
}
for(int i = 0; i < n - 1; i++){
mid.update(ord[s[0][i]], id[s[0][i]], 1);
}
int togo = 0, cnt = 0;
for(int i = 0; i < n - 1; i++){
for(int j = 0; j < m; j++){
int ans2 = mid.query(1, ord[s[j][i]], near[ord[s[j][i]]], 0, mid.off - 1, 1);
togo = max(togo, ans2);
}
if(togo == i)cnt++, togo++;
}
//int dep[N+2], sub[N+2], id[N+2], ord[N+2], near[N+2];
//vector<int> adj[N+2], order;
order.clear();
for(int i = 0; i < n; i++){
adj[i].clear();
dep[i] = 0;
sub[i] = 0;
ord[i] = 0;
near[i] = 0;
id[i] = 0;
}
return cnt;
}
// int main(){
// int tt = 1;
// //cin>>tt;
// while(tt--){
// cout<<solve(3, 1, {-1, 0, 0}, {{1, 2}});
// cout<<'\n';
// }
// }
