Tree Game

Time limit1sMemory limit64 MB

Summary

On a tree, players alternately move a token to an unchosen neighbor from Manco's start vertex; find all start vertices where Manco wins with optimal play.

Level: Medium7 of 10
Topics: Tree, Game theory, Dynamic programming, DFS
Solved: No attempts yet

Problem

Maňko and Kubko both love games and have discovered a new one: the tree game. First, Maňko chooses a vertex of a tree. Then, starting with Kubko, the players alternately choose a neighbor of the most recently chosen vertex that has not been chosen before. Play continues until a player cannot move; that player loses and the other one wins. Maňko moves first, but Kubko is a seasoned player who never makes a mistake. Determine every vertex from which Maňko can start the game and be guaranteed to win, no matter how Kubko plays.

Input

The first line contains a single integer $N$ ( $1 \le N \le 2\,000\,000$ ), the number of vertices in the tree; the vertices are numbered $1$ through $N$ . Each of the next $N-1$ lines contains one integer: the $i$ -th such line holds $a_i$ , meaning there is an edge joining vertex $(i+1)$ and vertex $a_i$ . It is guaranteed that $a_i \le i$ .

Output

Print every vertex from which Maňko can start and win regardless of Kubko's play, one per line, in ascending order.

Examples4

Example 1
Input
```
3
1
1
```
Expected output
```
2
3
```
Example 2
Input
```
6
1
1
1
4
5
```
Expected output
```
2
3
4
6
```
Example 3
Input
```
1
```
Expected output
```
1
```
Example 4
Input
```
6
1
1
1
1
1
```
Expected output
```
2
3
4
5
6
```