Preparando MOJI

Destruction of a Tree

1000ms 262144K

Description:

You are given a tree (a graph with n vertices and n - 1 edges in which it's possible to reach any vertex from any other vertex using only its edges).

A vertex can be destroyed if this vertex has even degree. If you destroy a vertex, all edges connected to it are also deleted.

Destroy all vertices in the given tree or determine that it is impossible.

Input:

The first line contains integer n (1 ≤ n ≤ 2·105) — number of vertices in a tree.

The second line contains n integers p1, p2, ..., pn (0 ≤ pi ≤ n). If pi ≠ 0 there is an edge between vertices i and pi. It is guaranteed that the given graph is a tree.

Output:

If it's possible to destroy all vertices, print "YES" (without quotes), otherwise print "NO" (without quotes).

If it's possible to destroy all vertices, in the next n lines print the indices of the vertices in order you destroy them. If there are multiple correct answers, print any.

Sample Input:

5
0 1 2 1 2

Sample Output:

YES
1
2
3
5
4

Sample Input:

4
0 1 2 3

Sample Output:

NO

Note:

In the first example at first you have to remove the vertex with index 1 (after that, the edges (1, 2) and (1, 4) are removed), then the vertex with index 2 (and edges (2, 3) and (2, 5) are removed). After that there are no edges in the tree, so you can remove remaining vertices in any order.

Informação

Codeforces

Provedor Codeforces

Código CF963B

Tags

constructive algorithmsdfs and similardpgreedytrees

Submetido 0

BOUA! 0

Taxa de BOUA's 0%

Datas 09/05/2023 09:33:40

Relacionados

Nada ainda