#include <bits/stdc++.h>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
using namespace std;
constexpr int inf = 1e9;
int DeletePlan( int N, int M, int K, int *A, int *B) {
int n = N + M;
vector<vector<int>> g(n);
for (int i = 0; i < N; ++i) {
g[A[i] + N].push_back(i);
}
for (int i = 1; i < M; ++i) {
g[B[i] + N].push_back(i + N);
}
vector<int> num(n), tail(n), euler(n + 1);
vector<vector<int>> back(n + 1);
int timer = 0;
function<void(int)> dfs = [&](int v) {
num[v] = tail[v] = ++timer;
euler[timer] = v;
for (int u : g[v]) dfs(u);
tail[v] = timer;
back[tail[v]].push_back(num[v]);
};
dfs(N);
vector<int> pref(n + 1);
for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + (euler[i] < N);
vector<vector<int>> dp(n + 1, vector<int>(K + 1, inf));
for (int i = 0; i <= n; ++i) dp[i][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= K; ++j) {
dp[i][j] = dp[i - 1][j];
for (int x : back[i]) {
int val = pref[i] - pref[x - 1];
if (val > j) continue;
dp[i][j] = min(dp[i][j], dp[x - 1][j - val] + 1);
}
}
}
return dp[n][K];
}
