September

The central square of Hangzhou has a famous ancient tree. It can be regarded as a rooted tree with $N$ nodes, indexed from $0$ to $N - 1$, where node $0$ is the root.

A node with no children is called a leaf node. Each time the ancient tree sheds leaves, it deletes one leaf node that exists at that moment. It may shed leaves several times on the same day.

There are $M$ volunteers, indexed from $0$ to $M - 1$, who guard the ancient tree. Each one independently records this year's leaf shedding with the following method.

Every day, collect the indices of all leaves that fell that day, and write them in any order after the records from earlier days.

For example, on the first day leaves $3$ and $4$ fall, so the record is $3, 4$ or $4, 3$. On the second day leaves $1$ and $2$ fall, so the record continues with $1, 2$ or $2, 1$. The final record can be any of $(3, 4, 1, 2)$, $(4, 3, 1, 2)$, $(3, 4, 2, 1)$, or $(4, 3, 2, 1)$.

The process lasts for $K$ days, with newly fallen leaves every day, until only the root node remains.

You are visiting Hangzhou in the middle of winter. Looking up at the bare branches of the ancient tree, you imagine the beautiful sight of falling leaves. You want to know how many days of falling leaves you could have seen this year, but you only have the records from the $M$ volunteers. From these records, find the maximum possible value of $K$.

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