/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include "september.h"
#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <vector>
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using namespace std;
#define ln '\n'
#define INFi 1e9
#define INFll 1e18
#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#define myassert(Expr, Msg) ;
#endif
size_t _n, _m;
vector<int> pa, ind;
vector<char> used;
vector<vector<int>> S, adj;
ll ans = -1;
inline void systemd() {
used.assign(_n, false);
adj.assign(_n, vector<int>(0));
for (int i = 1; i < _n; i++) {
adj[pa[i]].push_back(i);
adj[i].push_back(pa[i]);
}
ind.assign(_n, 0);
ans = -1;
}
void solve1() {
function<int(int)> dfs = [&](int v) { /// NOTE: dfs that assign used[v] = 1 for all of subtree v and gives maximum indexs at all of subtree on S[0]
if (used[v])
return ind[v];
used[v] = true;
int res = ind[v];
for (const auto &u : adj[v]) { //
if (pa[v] == u || used[u])
continue;
res = max(dfs(u), res);
}
return res;
};
myassert(S.size() == 1, "INPUT IS WRONG: S.size() is not one at _m == 1");
for (size_t i = 0; i < S[0].size(); i++) { /// NOTE: ind[x] says maximum indexs
ind[S[0][i]] = i;
}
ans = 0;
for (size_t i = 0; i < S[0].size();) { /// NOTE: for every v or S[0][i] if used[v] is 0 and sets i to max element
const int &v = S[0][i];
if (used[v]) {
i++;
continue;
}
ans++;
int j = dfs(v);
if (i >= j) {
i++;
continue;
} else {
for (int k = i + 1; k < j; k++) {
dbg(j);
j = max(j, dfs(S[0][k]));
}
}
}
myassert(!used[0], "WA: root is used");
}
char solve() {
function<int(int)> dfs = [&](int v) {
if (used[v])
return ind[v];
dbg(v);
used[v] = true;
int res = ind[v];
for (const auto &u : adj[v]) {
if (pa[v] == u || used[u])
continue;
res = max(dfs(u), res);
}
return res;
};
myassert(S.size() == _m, "INPUT IS WRONG: S.size() is not equal to _m");
for (size_t j = 0; j < _m; j++) {
for (size_t i = 0; i < S[j].size(); i++) {
ind[S[j][i]] = max<int>(ind[S[j][i]], i);
}
}
ans = 0;
dbg(ind);
for (size_t j = 0; j < 1; j++) {
for (size_t i = 0; i < S[j].size();) {
const int &v = S[j][i];
if (used[v]) {
i++;
continue;
}
ans++;
int indxs = dfs(v);
dbg(indxs);
if (i >= indxs) {
i++;
continue;
} else {
for (int j = 0; j < _m; j++) {
for (int k = i; k < indxs; k++) {
dbg(indxs);
int res = dfs(S[j][k]);
if (indxs < res) {
indxs = res;
j = 0;
}
}
}
}
}
}
myassert(!used[0], "WA: root is used");
return 1;
}
// Attack on titan<3
int solve(int N, int M, std::vector<int> __pa, std::vector<std::vector<int>> __S) {
_n = N, _m = M;
pa = __pa;
S = __S;
systemd();
if (M == 1) {
solve1();
myassert(ans >= 1, "WA: Answer must be greater than 0");
return ans;
}
solve();
myassert(ans >= 1, "WA: Answer must be greater than 0");
return ans;
}
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/
