재생목록 정리 게임

문제

음악 스트리밍 서비스의 라이브러리는 폴더와 재생목록이 이루는 트리 구조다. 노드에는 1번부터 N번까지 번호가 붙어 있고, 1번 노드는 라이브러리 전체를 뜻하는 루트이다. 2번 이상의 각 노드 i는 부모 노드 p_i를 가지며 p_i < i 이다. 두 사용자 A와 B가 라이브러리 정리 게임을 한다. A가 먼저 시작하고 번갈아 한 번씩 자기 차례를 진행한다. 자기 차례에는 아직 삭제되지 않은 노드 중 1번이 아닌 노드 하나를 골라, 그 노드와 그 노드의 모든 하위 노드를 한꺼번에 삭제한다. 1번 노드는 삭제할 수 없다. 자기 차례에 고를 수 있는 노드가 하나도 없는 사람이 패배한다. 두 사람은 모두 최선을 다한다. A가 이기는 경우, A가 첫 번째 차례에 고를 수 있는 노드 중 그 선택 이후 B가 어떻게 두든 A가 이길 수 있는 노드(필승 첫 수)의 개수와, 그러한 노드 중 가장 작은 번호를 구한다. B가 이기는 경우에는 B만 출력한다.

입력

첫 줄에 노드의 수 N (2 ≤ N ≤ 50,000)이 주어진다. 둘째 줄에 p_2, p_3, ..., p_N 이 공백으로 구분되어 주어진다. 모든 i에 대해 1 ≤ p_i < i 이다.

출력

B가 이기면 B 한 글자만 출력한다. A가 이기면 A, 필승 첫 수의 개수, 필승 첫 수 중 가장 작은 노드 번호를 공백으로 구분하여 한 줄에 출력한다.

4
1 2 2

A 1 2

4
1 1 1

A 3 2

5
1 1 2 2

B

출처: Devin.KR 자체 제작