루트 있는 트리 동형 분류

$N$개의 정점을 가진 루트 있는 트리가 주어진다. 트리의 루트는 정점 $0$이다. 정점 $i$의 부모는 $p _ i$이다. 루트를 선택하여 $N$개의 루트 있는 부분 트리를 얻게 된다. 이들을 루트 있는 트리의 동형 여부에 따라 분류하라.

이제 다음 조건을 만족하는 서로 다른 부분 트리의 개수 $K$와 정수 수열 $a _ 0 , a _ 1 , \ldots , a _ {N-1}$을 출력한다.

• $0 \leq a _ i \lt K$
• 루트가 $i$와 $j$인 $2$ 부분 트리가 동형일 때, 그리고 그럴 때에만 $a _ i = a _ j$이다.

제약 조건

• $1 \leq N \leq 500000$
• $0 \leq p _ i \lt i$

$N$
$p _ 1$ $p _ 2$ $\ldots$ $p _ {N-1}$

$K$
$a _ 0$ $a _ 1$ $\ldots$ $a _ {N-1}$

해가 여러 개라면, 그중 아무거나 출력한다.