#include "september.h"
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <climits>
#include <bitset>
#include <vector>
#include <queue>
#include <set>
int dfs(std::vector<int>& F, std::set<int>& leafs, int* depth, std::set<int>* childs, int* childc, int n) {
if (depth[n] != INT_MAX) return depth[n];
if (F[n] == -1) return 0;
childs[F[n]].insert(n);
childc[F[n]]++;
auto parent = leafs.find(F[n]);
if (parent != leafs.end())
leafs.erase(parent);
depth[n] = dfs(F, leafs, depth, childs, childc, F[n]) + 1;
return depth[n];
}
void add_needed(std::set<int>* childs, std::bitset<100005>& rem, int n, std::set<int>& target) {
for (int c: childs[n]) {
if (rem[c]) continue;
rem[c] = 1;
target.insert(c);
add_needed(childs, rem, n, target);
}
}
#define pt std::pair<std::pair<int, int>, int>
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
std::set<int> leafs, childs[N];
int childc[N];
int depth[N];
for (int x = 0; x < N; x++)
depth[x] = INT_MAX, leafs.insert(x), childc[x] = 0;
for (int x = 1; x < N; x++)
dfs(F, leafs, depth, childs, childc, x);
int days = 0,
timer = 0,
topday = 0;
std::priority_queue<
pt,
std::vector<pt>,
std::greater<pt>
> parsed;
for (int x = 0; x < M; x++)
parsed.push({{0, timer++}, x});
std::bitset<100005> trem;
std::set<int> target, repls[N];
while (parsed.top().first.first < (N - 1)) {
auto p = parsed.top(); parsed.pop();
// std::cout << "Member: " << p.second << "\n";
if (topday == p.first.first) {
int leaf = S[p.second][topday++];
target.insert(leaf);
if (childc[leaf] > 0) {
add_needed(childs, trem, leaf, target);
if (F[leaf] != -1)
childc[F[leaf]]--;
}
days++;
}
int tsize = target.size();
while (1) {
while (repls[p.second].size() < target.size())
repls[p.second].insert(S[p.second][p.first.first++]);
if (repls[p.second] != target) {
for (int v: repls[p.second]) {
if (target.find(v) != target.end())
continue;
if (childc[v] > 0) {
add_needed(childs, trem, v, target);
if (F[v] != -1)
childc[F[v]]--;
}
trem[v] = 1;
target.insert(v);
}
continue;
} break;
}
// std::cout << "target: ";
// for (int a: target)
// std::cout << " " << a;
// std::cout << "\n";
parsed.push({{target.size(), timer++}, p.second});
}
return days;
}
