트리 게임

시간 제한1초메모리 제한64 MB

요약

트리에서 토큰을 아직 방문하지 않은 이웃으로 번갈아 옮기며, 마니코가 먼저 시작해 최선의 플레이로 이기는 모든 시작 정점을 구한다.

난이도: 보통10점 중 7점
유형: 트리, 게임 이론, 동적 계획법, DFS
정답자: 아직 제출이 없습니다

문제

마뇨(Maňko)와 쿠브코(Kubko)는 게임을 매우 좋아하는데, 새로운 게임인 트리 게임을 발견했습니다. 먼저 마뇨가 트리의 정점 하나를 고릅니다. 그다음부터는 쿠브코를 시작으로 두 사람이 번갈아 가며, 가장 마지막에 고른 정점의 이웃 중 아직 고르지 않은 정점 하나를 고릅니다. 어느 한 사람이 더 이상 고를 수 없게 되면 그 사람이 지고 상대가 이깁니다. 마뇨가 먼저 시작하지만, 쿠브코는 실수 없이 완벽하게 두는 노련한 상대입니다. 마뇨가 게임을 시작해서, 쿠브코가 어떻게 두더라도 반드시 이길 수 있는 모든 시작 정점을 구하세요.

입력

첫째 줄에 트리의 정점 수 $N$ ( $1 \le N \le 2\,000\,000$ )이 주어집니다. 정점은 $1$ 번부터 $N$ 번까지 번호가 매겨져 있습니다. 이어지는 $N-1$ 개의 줄 중 $i$ 번째 줄에는 정수 $a_i$ 가 하나 주어지며, 이는 정점 $(i+1)$ 과 정점 $a_i$ 를 잇는 간선이 있음을 뜻합니다. 항상 $a_i \le i$ 임이 보장됩니다.

출력

마뇨가 시작해서 쿠브코가 어떻게 두더라도 이길 수 있는 모든 정점을 오름차순으로 한 줄에 하나씩 출력하세요.

예제4

예제 1
입력
```
3
1
1
```
예상 출력
```
2
3
```
예제 2
입력
```
6
1
1
1
4
5
```
예상 출력
```
2
3
4
6
```
예제 3
입력
```
1
```
예상 출력
```
1
```
예제 4
입력
```
6
1
1
1
1
1
```
예상 출력
```
2
3
4
5
6
```