September

항저우 중심 광장에는 유명한 고목이 있다. 이 나무는 노드 $N$개로 이루어진 뿌리 달린 트리로 볼 수 있으며, 노드는 $0$부터 $N - 1$까지 번호가 붙고 뿌리는 노드 $0$이다.

자식이 없는 노드를 리프 노드라고 한다. 고목은 잎을 떨굴 때마다 그 시점에 존재하는 리프 노드 하나를 골라 삭제한다. 같은 날에 여러 번 잎을 떨굴 수도 있다.

$0$부터 $M - 1$까지 번호가 붙은 자원봉사자 $M$명이 이 고목을 지킨다. 각자 독립적으로 다음 방법에 따라 올해의 낙엽 상황을 기록한다.

매일 그날 떨어진 잎들의 번호를 모두 모아, 이전 날의 기록 뒤에 어떤 순서로든 이어서 적는다.

예를 들어 첫째 날 잎 $3$과 $4$가 떨어지면 $3, 4$ 또는 $4, 3$으로 적는다. 둘째 날 잎 $1$과 $2$가 떨어지면 $1, 2$ 또는 $2, 1$을 이어서 적는다. 최종 기록은 $(3, 4, 1, 2)$, $(4, 3, 1, 2)$, $(3, 4, 2, 1)$, $(4, 3, 2, 1)$ 중 하나가 될 수 있다.

이 과정은 매일 새로 떨어진 잎이 있는 상태로 $K$일 동안 계속되며, 뿌리 노드만 남으면 끝난다.

겨울에 항저우를 여행하고 있다. 앙상한 고목의 가지를 올려다보니 잎이 떨어지는 아름다운 풍경이 떠오른다. 올해 잎이 며칠이나 떨어지는 것을 볼 수 있었는지 알고 싶은데, 가진 것은 $M$명의 자원봉사자가 남긴 기록뿐이다. 이 기록으로부터 가능한 $K$의 최댓값을 구하라.

• $2 ≤ N ≤ 10^5$.
• $1 ≤ M ≤ 5$.
• $\sum NM ≤ 8 \times 10^5$.
• $F[0] = -1$. $1 ≤ i ≤ N - 1$인 각 $i$에 대해 $0 ≤ F[i] ≤ i - 1$이다.
• $1 ≤ i ≤ M - 1$인 각 $i$에 대해 배열 $S[i]$는 $1, 2, \dots, N - 1$의 순열이다.
• $F$는 노드 $0$을 뿌리로 하는 뿌리 달린 트리를 나타냄이 보장된다.