Ancient Tree Leaf Fall Day Maximization

You are given an ancient tree with (N) nodes numbered from (0) to (N-1) and a parent array (F) where (F[0] = -1) and for (1 \le i \le N-1), (F[i]) is the parent of node (i). The tree undergoes a process where, on each day, all leaves (nodes without any children) fall. This process continues until only the root remains. In addition, there are (M) volunteers. Each volunteer (i) records an ordering (S[i]) (of length (N-1)) of the nodes that fell (the root is never recorded). Although the recorded orders might vary among volunteers, they are all consistent with at least one valid removal order of the tree.

Your task is to implement the function

[ int solve(int N, int M, std::vector F, std::vector<std::vector> S); ]

that returns an integer representing the maximum possible number of days (K) (i.e. the maximum possible leaf falling day) such that there exists a valid leaf removal process for the given tree, which is also compatible with the volunteer records.

Note: Since the function may be called multiple times, be careful to clear any global state between calls.

inputFormat

The function receives the following parameters:

• (N) (int): The number of nodes in the tree. • (M) (int): The number of volunteers. • (F) (vector): An array of length (N) where (F[0] = -1) and for every (1 \le i \le N-1), (F[i]) is the parent node of node (i). • (S) (vector<vector>): A 2D array of size (M \times (N-1)) where (S[i][j]) represents the (j)-th node (0-indexed) recorded by volunteer (i).

outputFormat

Return an integer representing the maximum possible number of days the leaves can fall (i.e. the maximum possible leaf removal day) under some valid removal order of the tree that is consistent with the volunteer records.

sample

2
1
-1 0
1

1