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} $, $ n \geq 1 $, be the number of vertices in a tree.
Let $ P = (p_1, p_2, \dots, p_n) $ be a sequence of integers where $ p_i \in \{0, 1, \dots, n\} $, defining the tree as follows:
- For each $ i \in \{1, \dots, n\} $, if $ p_i \neq 0 $, then there is an undirected edge between vertex $ i $ and vertex $ p_i $.
- The graph is guaranteed to be a tree (connected, acyclic, $ n-1 $ edges).
Let $ \deg(v) $ denote the degree of vertex $ v \in \{1, \dots, n\} $.
**Constraints**
1. $ 1 \leq n \leq 2 \cdot 10^5 $
2. The graph defined by $ P $ is a tree.
3. A vertex $ v $ can be destroyed **only if** $ \deg(v) $ is even.
4. Upon destruction of vertex $ v $, all edges incident to $ v $ are removed, reducing the degree of all its neighbors by 1.
5. The process continues until all vertices are destroyed or no more vertices can be destroyed.
**Objective**
Determine whether there exists an order $ v_1, v_2, \dots, v_n $ of vertex destruction such that:
- At the time of destroying $ v_i $, $ \deg(v_i) $ is even.
- After each destruction, edge deletions are applied and degrees are updated accordingly.
- All $ n $ vertices are destroyed.
If such an order exists:
- Output "YES", followed by the sequence $ v_1, v_2, \dots, v_n $.
- Otherwise, output "NO".
API Response (JSON)
{
"problem": {
"name": "B. 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": "CF963B"
},
"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} $, $ n \\geq 1 $, be the number of vertices in a tree. \nLet $ P = (p_1, p_2, \\dots, p_n) $ be a sequence of integers where $ p_i \\in \\{0, 1, \\dots, n\\} $, defi...",
"is_translate": false,
"language": "Formal"
}
]
}