너도밤나무

Vétyem 숲은 색이 다양한 나무가 많기로 유명한 숲이다. 이 숲에서 가장 오래되고 키가 큰 너도밤나무 중 하나를 Ős Vezér라고 부른다.

Ős Vezér는 $N$개의 노드와 $N-1$개의 간선으로 이루어진 트리로 모델링할 수 있다. 노드는 $0$부터 $N-1$까지 번호가 붙고, 간선은 $1$부터 $N-1$까지 번호가 붙는다. 각 간선은 서로 다른 두 노드를 잇는다. 구체적으로, 간선 $i$ ($1 \le i < N$)는 노드 $i$와 노드 $P[i]$를 잇는다. 여기서 $0 \le P[i] < i$이다. 노드 $P[i]$를 노드 $i$의 부모라 하고, 노드 $i$를 노드 $P[i]$의 자식이라 한다.

각 간선에는 $1$부터 $M$까지의 색이 하나씩 있다. 간선 $i$의 색은 $C[i]$이다. 서로 다른 간선이 같은 색을 가질 수 있다. 편의상 $P[0] = -1$, $C[0] = 0$으로 둔다. 다만 노드 $0$의 위쪽에는 간선이 없다.

예를 들어 Ős Vezér의 노드가 $N = 18$개이고 색이 $M = 3$가지이며, $P = [-1, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 10, 11, 11]$, $C = [0, 1, 2, 3, 1, 2, 3, 1, 3, 3, 2, 1, 1, 2, 2, 1, 2, 3]$라고 하자. 이 트리는 아래 그림과 같다.

Árpád는 부분트리를 연구한다. $0 \le r < N$인 각 $r$에 대해, 노드 $r$의 부분트리는 다음 성질을 만족하는 노드들의 집합 $T(r)$이다. 노드 $r$은 $T(r)$에 속한다. $T(r)$에 속한 노드 $x$의 자식은 모두 $T(r)$에 속한다. 그 밖의 노드는 $T(r)$에 속하지 않는다. $T(r)$의 크기는 $|T(r)|$로 쓴다.

$r$을 고정하고 $T(r)$의 노드들을 나열한 순열 $v_0, v_1, \ldots, v_{|T(r)|-1}$을 생각하자. $1 \le i < |T(r)|$인 각 $i$에 대해, $f(i)$는 색 $C[v_i]$가 수열 $C[v_1], C[v_2], \ldots, C[v_{i-1}]$에 나타나는 횟수이다. $f(1)$은 항상 $0$이다.

다음 두 조건이 모두 성립하면 이 순열은 아름다운 순열이다.

• $v_0 = r$이다.
• $1 \le i < |T(r)|$인 각 $i$에 대해, $v_i$의 부모는 $v_{f(i)}$이다.

$T(r)$의 노드들에 대한 아름다운 순열이 존재할 때, 그리고 그때에만 $T(r)$은 아름다운 부분트리이다. 노드가 하나뿐인 부분트리는 항상 아름답다.

예시 트리에서 $T(0)$과 $T(3)$은 아름답지 않다. $T(14)$는 노드가 하나뿐이므로 아름답다. $T(1)$도 아름답다. 수열 $[v_0, v_1, v_2, v_3, v_4, v_5, v_6] = [1, 4, 5, 12, 13, 6, 14]$는 $T(1)$의 노드들을 나열한 순열이다. 아래 그림에서 각 노드의 라벨은 그 노드가 순열에서 놓인 인덱스이다.

이 순열을 확인해 보자. $v_0 = 1$이다. $C[v_1] = C[4] = 1$은 빈 수열에 $0$번 나타나므로 $f(1) = 0$이고, 노드 $4$의 부모는 노드 $1$이다. $C[v_2] = C[5] = 2$는 $[1]$에 $0$번 나타나므로 $f(2) = 0$이고, 노드 $5$의 부모는 노드 $1$이다. $C[v_3] = C[12] = 1$은 $[1, 2]$에 1번 나타나므로 $f(3) = 1$이고, 노드 $12$의 부모는 노드 $4$이다. $C[v_4] = C[13] = 2$는 $[1, 2, 1]$에 1번 나타나므로 $f(4) = 1$이고, 노드 $13$의 부모는 노드 $4$이다. $C[v_5] = C[6] = 3$은 $[1, 2, 1, 2]$에 $0$번 나타나므로 $f(5) = 0$이고, 노드 $6$의 부모는 노드 $1$이다. $C[v_6] = C[14] = 2$는 $[1, 2, 1, 2, 3]$에 2번 나타나므로 $f(6) = 2$이고, 노드 $14$의 부모는 노드 $5$이다. 이 순열은 아름다우므로 $T(1)$은 아름답다.

Ős Vezér의 모든 부분트리에 대해 아름다운 부분트리인지 판정하라.

• $3 \le N \le 200\,000$
• $2 \le M \le 200\,000$
• $0 \le P[i] < i$ ($1 \le i < N$인 각 $i$에 대해)
• $1 \le C[i] \le M$ ($1 \le i < N$인 각 $i$에 대해)
• $P[0] = -1$, $C[0] = 0$