English · Original
Chinese · Translation
Formal · Original
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 _p_1, _p_2, ..., _p__n_ (0 ≤ _p__i_ ≤ _n_). If _p__i_ ≠ 0 there is an edge between vertices _i_ and _p__i_. 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.
[samples]
## 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.
<center></center>
给你一棵树（一个具有 #cf_span[n] 个顶点和 #cf_span[n - 1] 条边的图，其中仅通过其边可以从任意顶点到达任意其他顶点）。
如果一个顶点的度为偶数，则可以销毁该顶点。当你销毁一个顶点时，所有与之相连的边也会被删除。
请销毁给定树中的所有顶点，或确定这是不可能的。
第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2·105]) —— 树中顶点的数量。
第二行包含 #cf_span[n] 个整数 #cf_span[p1, p2, ..., pn] (#cf_span[0 ≤ pi ≤ n])。如果 #cf_span[pi ≠ 0]，则顶点 #cf_span[i] 和 #cf_span[pi] 之间有一条边。保证给定图是一棵树。
如果可以销毁所有顶点，请输出 "_YES_"（不含引号），否则输出 "_NO_"（不含引号）。
如果可以销毁所有顶点，请在接下来的 #cf_span[n] 行中按销毁顺序输出顶点的索引。如果有多个正确答案，输出任意一个即可。
在第一个示例中，首先必须移除索引为 1 的顶点（之后边 (1, 2) 和 (1, 4) 被删除），然后移除索引为 2 的顶点（边 (2, 3) 和 (2, 5) 也被删除）。此后树中不再有边，因此你可以按任意顺序移除剩余顶点。
## Input
第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2·105]) —— 树中顶点的数量。第二行包含 #cf_span[n] 个整数 #cf_span[p1, p2, ..., pn] (#cf_span[0 ≤ pi ≤ n])。如果 #cf_span[pi ≠ 0]，则顶点 #cf_span[i] 和 #cf_span[pi] 之间有一条边。保证给定图是一棵树。
## Output
如果可以销毁所有顶点，请输出 "_YES_"（不含引号），否则输出 "_NO_"（不含引号）。如果可以销毁所有顶点，请在接下来的 #cf_span[n] 行中按销毁顺序输出顶点的索引。如果有多个正确答案，输出任意一个即可。
[samples]
## Note
在第一个示例中，首先必须移除索引为 1 的顶点（之后边 (1, 2) 和 (1, 4) 被删除），然后移除索引为 2 的顶点（边 (2, 3) 和 (2, 5) 也被删除）。此后树中不再有边，因此你可以按任意顺序移除剩余顶点。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of vertices in a tree.
Let $ G = (V, E) $ be a tree with $ V = \{1, 2, \dots, n\} $ and $ |E| = n - 1 $.
Let $ p = (p_1, p_2, \dots, p_n) $ be a list where $ p_i \in \{0\} \cup V $, and for each $ i \in V $, if $ p_i \ne 0 $, then $ \{i, p_i\} \in E $.
Let $ \deg(v) $ denote the degree of vertex $ v \in V $ in the current graph.
**Constraints**
1. $ 1 \le n \le 2 \cdot 10^5 $
2. The graph $ G $ is a tree (connected, acyclic, undirected).
3. $ p_i = 0 $ iff vertex $ i $ has no parent in the input encoding (i.e., $ i $ is not connected to any vertex with smaller index in the encoding; but the graph is undirected and tree-structured).
4. The adjacency structure defined by $ p $ forms a valid tree.
**Objective**
Determine whether there exists an ordering $ v_1, v_2, \dots, v_n $ of $ V $ such that at the time of destruction of $ v_k $, $ \deg(v_k) $ is even.
Upon destruction of $ v_k $, all edges incident to $ v_k $ are removed, reducing the degree of its neighbors by 1.
If such an ordering exists:
- Output "YES", followed by the sequence $ v_1, v_2, \dots, v_n $.
- Otherwise, output "NO".
API Response (JSON)
{
"problem": {
"name": "D. Destruction of a Tree",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF964D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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).\n\nA vertex can be destroyed if this vertex has ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "给你一棵树（一个具有 #cf_span[n] 个顶点和 #cf_span[n - 1] 条边的图，其中仅通过其边可以从任意顶点到达任意其他顶点）。\n\n如果一个顶点的度为偶数，则可以销毁该顶点。当你销毁一个顶点时，所有与之相连的边也会被删除。\n\n请销毁给定树中的所有顶点，或确定这是不可能的。\n\n第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2·105]) —— 树中顶点...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of vertices in a tree. \nLet $ G = (V, E) $ be a tree with $ V = \\{1, 2, \\dots, n\\} $ and $ |E| = n - 1 $. \nLet $ p = (p_1, p_2, \\dots, p_n)...",
"is_translate": false,
"language": "Formal"
}
]
}