#include "bits/stdc++.h"
using namespace std;
typedef long long int ll;
int dsuParents[100005];
int dsuSizes[100005];
bool visited[100005];
int getParent(int node){
// cout << "[pop]" << node << '\n';
if(dsuParents[node] == -1 || dsuParents[node] == node) return node;
dsuParents[node] = getParent(dsuParents[node]);
return dsuParents[node];
}
void createNode(int node){
dsuParents[node] = node;
dsuSizes[node] = 1;
}
bool merge(int a, int b){
int pA = getParent(a);
int pB = getParent(b);
if (pA == pB) return false;
if(dsuSizes[pA] > dsuSizes[pB]) swap(pA, pB);
dsuParents[pA] = pB;
dsuSizes[pB] += dsuSizes[pA];
return true;
}
int solveM(int N, vector<int> &F, vector<int> S, vector<unordered_set<int>> &adjList){
for(int i=0;i<100005;i++){
dsuParents[i]=-1;
dsuSizes[i]=0;
visited[i]=false;
}
visited[0] = true;
int components = 1;
int counts = 0;
for(int i = S.size() - 1; i >= 0; i--){
components++;
// cout << "Creaiting: " << S[i] << '\n';
createNode(S[i]);
for(int node : adjList[S[i]]){
if(visited[node] && merge(S[i], node)){
components--;
// cout << "Joining: " << node << " " << S[i] << '\n';
}
}
// cout << "Components: " << components << '\n';
visited[S[i]] = true;
if(components == 1) counts++;
}
return counts;
}
int solve(int N, int M, vector<int> F,vector<vector<int>> S){
int minSize = 99999999;
vector<unordered_set<int>> adjList(N);
for(int i = 1; i < N; i++){
adjList[i].insert(F[i]);
adjList[F[i]].insert(i);
}
for(int j = 0; j < M; j++){
// cout << "tooot\n";
minSize = min(minSize, solveM(N, F, S[j], adjList));
// cout << "Test" << minSize << '\n';
}
return minSize;
}
// int main(){
// cout << "poop\n";
// cout << solve(5, 2, {-1, 0, 0, 1, 1}, {{1, 2, 3, 4}, {4, 1, 2, 3}}) << '\n';
// return 0;
// }
