팀 코딩

EGOI(Eindhoven Gigantic Open-Source Institute)는 계층 구조가 매우 뚜렷한 회사다. CEO인 Anneke를 제외한 나머지 $N-1$명의 직원에게는 각자 보고할 직속 상사가 한 명씩 있으며, 계층 구조에 순환은 없다. 회사의 계층 구조는 Anneke를 루트로 하는 트리로 볼 수 있다. 회사는 다양성이 높아서 직원들은 $K$가지 프로그래밍 언어 중 하나로 코딩하며, 모든 직원은 선호하는 프로그래밍 언어가 정확히 하나씩 있다.

Anneke에게는 한 팀에 맡길 큰 새 프로젝트가 있다. 그녀는 이 프로젝트에 가능한 한 많은 인력을 투입하려 한다. 팀을 정하기 위해 다음 과정을 따른다.

1. 팀을 이끌 리더를 한 명 고른다. 리더가 선호하는 프로그래밍 언어가 프로젝트의 구현 언어가 된다. 리더의 서브트리에 있으면서 같은 언어를 선호하는 직원은 모두 프로젝트에 참여한다.
2. 같은 언어를 선호하는 직원을 팀으로 옮겨 참여 인원을 늘린다. 이를 위해 다음 교환 연산을 원하는 만큼 몇 번이든 할 수 있다.
   1. 두 직원을 고른다.
      1. 리더의 서브트리에 있으면서 리더와 선호 언어가 다른 직원 한 명.
      2. 현재 그 서브트리 밖에 있으면서 리더와 선호 언어가 같은 직원 한 명. 이 직원은 앞서 고른 직원과 같은 레벨이어야 한다. 즉 Anneke까지 이어지는 보고 체인에서 거치는 상사 수가 같아야 하며, 트리로 보면 두 직원은 같은 깊이에 있어야 한다.
   2. 고른 두 직원만 회사 계층에서 자리를 맞바꾼다. 다른 직원은 옮겨지지 않는다. 두 직원에게 보고하던 직원들은 제자리에 있고, 보고 대상만 바뀐다. 아래 그림에서 리더를 직원 4로 정했을 때 직원 3과 2는 교환할 수 있지만 직원 1과 8은 교환할 수 없다.

교환을 몇 번이든 반복해 도달할 수 있는, 리더를 포함한 프로젝트 참여 직원의 최대 인원과 그 인원에 도달하는 데 필요한 최소 교환 횟수를 구하라.

첫 줄에 두 정수 $N$과 $K$가 주어진다. $N$은 EGOI 직원 수, $K$는 직원들이 사용할 수 있는 프로그래밍 언어 수다. 직원은 $0$부터 $N-1$까지 번호가 붙으며, CEO Anneke의 번호는 $0$이다. 다음 줄에는 $N$개의 정수 $\ell_i$($0 \le \ell_i < K$)가 주어지며, 이는 각 직원이 선호하는 프로그래밍 언어다. 다음 $N-1$개의 줄에는 회사 구조가 주어진다. $i$번째 줄에는 직원 $i$의 직속 상사 $b_i$($0 \le b_i < N$)가 정수 하나로 주어진다. $i$는 $1$부터 $N$까지이며, CEO인 Anneke는 상사가 없기 때문이다.

정수 두 개 $P$와 $S$를 한 줄에 출력한다. $P$는 교환을 몇 번 하든 도달할 수 있는, 리더를 포함한 프로젝트 참여 직원의 최대 인원이다. $S$는 그 인원에 도달하는 데 필요한 교환 횟수의 최솟값이다.

• $1 \le N \le 10^5$.
• $1 \le K \le N$.

처음 두 예시에서 회사 구조는 다음과 같다. 무늬는 프로그래밍 언어를 뜻한다(0은 줄무늬, 1은 점무늬, 2는 무늬 없음).

첫 번째 예시에서 직원 1을 리더로 고르면 같은 언어를 선호하는 직원 4가 함께 참여하며, 더 개선할 교환은 없다. 두 번째 예시에서는 회사 전체에 언어 0을 선호하는 직원이 3명 있는데, 이는 Anneke가 선호하는 언어이기도 하다. Anneke를 리더로 고르면 교환 없이 3명의 팀이 된다.

세 번째 예시에서는 직원 4를 리더로 고른다. 그다음 직원 1과 8, 직원 2와 3이 자리를 맞바꾸면, 직원 4와 같은 언어(언어 2, 노란색 무늬 없음)를 선호하는 직원이 4명이 된다. 네 번째 예시에서는 직원 6을 리더로 고르고, 직원 4와 7, 직원 1과 5를 교환해 최대 인원에 도달한다. 리더를 먼저 정해야 하므로, 리더를 고르기 전에 직원 6과 3을 교환해 4명을 만들 수는 없다.