Problem Description

In the central square of Hangzhou, there is a famous ancient tree. This ancient tree can be viewed as a rooted tree with $N$ nodes, numbered from $0$ to $N - 1$, where node $0$ is the root.

A node with no children is called a leaf. Each time the tree sheds leaves, it chooses one current leaf node and deletes it. In one day, the tree may shed leaves multiple times.

There are $M$ volunteers (numbered from $0$ to $M - 1$) who take care of the ancient tree. Each volunteer independently records the leaf-shedding situation of this year in the following way:

Each day, they collect the numbers of all newly fallen leaves (that is, the numbers of nodes deleted that day), and then write them in an arbitrary order after the previously written leaf numbers.

For example, on the first day, leaves $3$ and $4$ fall, so they write down $3, 4$ or $4, 3$. On the second day, leaves $1$ and $2$ fall, so they continue by writing $1, 2$ or $2, 1$. The final record may be any one of $(3, 4, 1, 2)$, $(4, 3, 1, 2)$, $(3, 4, 2, 1)$, or $(4, 3, 2, 1)$.

This process continues for $K$ days, with new leaves falling every day, until only the root node remains.

During your journey, you pass through Hangzhou. Now it is already midwinter. Looking up at the bare branches of the ancient tree, you cannot help but recall the beautiful scene of falling leaves.

You want to know on how many days it was possible to see leaves falling this year, but you can only find the records of the $M$ volunteers. Try to infer the maximum possible value of $K$ from these records.

Interaction

Please do not submit using C++14(GCC9).

You do not need to include the library september.h at the beginning of your program.

You only need to implement the following function:

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

• $N$: the number of nodes of the ancient tree.
• $M$: the number of volunteers.
• $F$: an array of length $N$. For $1 \le i \le N - 1$, $F[i]$ is the index of the parent of node $i$. $F[0]$ is always $-1$.
• $S$: an array of length $M$. Each element of $S$ is an array of length $N - 1$. $S[i][j]$ is the $j$-th node number recorded by volunteer $i$ (starting from $0$).
• This function must return an integer, meaning the maximum possible value of $K$ according to the rules above (i.e. the maximum possible number of days with leaf shedding).
• For each test case, the interaction library may call this function more than once. Each call should be handled as a new, independent situation.

Note: Since the function may be called multiple times, you should be careful about the effect of leftover data from previous calls on later calls, especially the state of global variables.

Input Format

The sample grader reads input in the following format:

• Line $1$: $T$

For each of the next $T$ test cases:

• Line $1$: $N\ M$
• Line $2$: $F[1]\ F[2]\ \ldots\ F[N - 1]$
• Line $3 + i\ (0 \le i \le M - 1)$: $S[i][0]\ S[i][1]\ S[i][2]\ \ldots\ S[i][N - 2]$

Output Format

The sample grader prints your answer in the following format:

For each test case:

• Line $1$: the return value of function solve.

1
3 1
0 0
1 2

2

1
5 2
0 0 1 1 
1 2 3 4
4 1 2 3

1

Hint

Sample Explanation

For sample 1, consider the following call:

solve(3, 1, {-1, 0, 0}, {{1, 2}});

The corresponding tree is shown below:

Leaves $1$ and $2$ may fall on the same day, or leaf $1$ falls first on day 1 and then leaf $2$ falls on day 2. The number of days with leaf shedding is at most $2$.

Therefore, the program should return $2$.

For sample 2, consider the following call:

solve(5, 2, {-1, 0, 0, 1, 1}, {{1, 2, 3, 4}, {4, 1, 2, 3}});

The corresponding tree is shown below:

Assume there are at least $2$ days with leaf shedding. From the volunteers' records, leaf $4$ would fall on different days (the first day and the last day), which is a contradiction.

Therefore, the program should return $1$.

Constraints

• $2 \le N \le 10^5$
• $1 \le M \le 5$
• $\sum NM \le 8 \times 10^5$
• $F[0] = -1$, and for $1 \le i \le N - 1$, $0 \le F[i] \le i - 1$
• For $1 \le i \le M - 1$, the array $S[i]$ is a permutation of $1, 2, \ldots , N - 1$
• It is guaranteed that $F$ describes a rooted tree with node $0$ as the root.

The detailed additional constraints and scores of subtasks are shown in the table below.

Translated by ChatGPT 5