{"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 even degree. If you destroy a vertex, all edges connected to it are also deleted.\n\nDestroy all vertices in the given tree or determine that it is impossible.\n\n## Input\n\nThe first line contains integer _n_ (1 ≤ _n_ ≤ 2·105) — number of vertices in a tree.\n\nThe 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.\n\n## Output\n\nIf it's possible to destroy all vertices, print \"_YES_\" (without quotes), otherwise print \"_NO_\" (without quotes).\n\nIf 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.\n\n[samples]\n\n## Note\n\nIn 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.\n\n<center>![image](https://espresso.codeforces.com/6e12cad71c744a2da8773d51510c1273282d8ab6.png)</center>","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]) —— 树中顶点的数量。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[p1, p2, ..., pn] (#cf_span[0 ≤ pi ≤ n])。如果 #cf_span[pi ≠ 0]，则顶点 #cf_span[i] 和 #cf_span[pi] 之间有一条边。保证给定的图是一棵树。\n\n如果可以销毁所有顶点，请输出 \"_YES_\"（不含引号），否则输出 \"_NO_\"（不含引号）。\n\n如果可以销毁所有顶点，则在接下来的 #cf_span[n] 行中按销毁顺序输出顶点的索引。如果有多个正确答案，输出任意一个即可。\n\n在第一个例子中，首先必须移除索引为 1 的顶点（移除后，边 (1, 2) 和 (1, 4) 被删除），然后移除索引为 2 的顶点（边 (2, 3) 和 (2, 5) 被删除）。之后树中不再有边，因此可以按任意顺序移除剩余顶点。\n\n## Input\n\n第一行包含整数 #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] 之间有一条边。保证给定的图是一棵树。\n\n## Output\n\n如果可以销毁所有顶点，请输出 \"_YES_\"（不含引号），否则输出 \"_NO_\"（不含引号）。如果可以销毁所有顶点，则在接下来的 #cf_span[n] 行中按销毁顺序输出顶点的索引。如果有多个正确答案，输出任意一个即可。\n\n[samples]\n\n## Note\n\n在第一个例子中，首先必须移除索引为 1 的顶点（移除后，边 (1, 2) 和 (1, 4) 被删除），然后移除索引为 2 的顶点（边 (2, 3) 和 (2, 5) 被删除）。之后树中不再有边，因此可以按任意顺序移除剩余顶点。","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\\} $, defining the tree as follows:  \n- 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 $.  \n- The graph is guaranteed to be a tree (connected, acyclic, $ n-1 $ edges).\n\nLet $ \\deg(v) $ denote the degree of vertex $ v \\in \\{1, \\dots, n\\} $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\cdot 10^5 $  \n2. The graph defined by $ P $ is a tree.  \n3. A vertex $ v $ can be destroyed **only if** $ \\deg(v) $ is even.  \n4. Upon destruction of vertex $ v $, all edges incident to $ v $ are removed, reducing the degree of all its neighbors by 1.  \n5. The process continues until all vertices are destroyed or no more vertices can be destroyed.\n\n**Objective**  \nDetermine whether there exists an order $ v_1, v_2, \\dots, v_n $ of vertex destruction such that:  \n- At the time of destroying $ v_i $, $ \\deg(v_i) $ is even.  \n- After each destruction, edge deletions are applied and degrees are updated accordingly.  \n- All $ n $ vertices are destroyed.\n\nIf such an order exists:  \n- Output \"YES\", followed by the sequence $ v_1, v_2, \\dots, v_n $.  \n- Otherwise, output \"NO\".","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF963B","tags":["constructive algorithms","dfs and similar","dp","greedy","trees"],"sample_group":[["5\n0 1 2 1 2","YES\n1\n2\n3\n5\n4"],["4\n0 1 2 3","NO"]],"created_at":"2026-03-03 11:00:39"}}