Codeforces Round #475 (Div. 1) B. Destruction of a Tree

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.

Examples

input

Copy

5
0 1 2 1 2

output

Copy

YES
1
2
3
5
4

input

Copy

4
0 1 2 3

output

Copy

NO

思路：贪心消除最靠近叶子的节点。因为如果最靠近叶子的偶数度节点晚于父节点消除，则父节点消除后此节点度数变为奇数，且其所有子节点度数都为奇数，就再也消除不了了。

 1 #include <iostream>
 2 #include <fstream>
 3 #include <sstream>
 4 #include <cstdlib>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <string>
 8 #include <cstring>
 9 #include <algorithm>
10 #include <queue>
11 #include <stack>
12 #include <vector>
13 #include <set>
14 #include <map>
15 #include <list>
16 #include <iomanip>
17 #include <cctype>
18 #include <cassert>
19 #include <bitset>
20 #include <ctime>
21 
22 using namespace std;
23 
24 #define pau system("pause")
25 #define ll long long
26 #define pii pair<int, int>
27 #define pb push_back
28 #define mp make_pair
29 #define clr(a, x) memset(a, x, sizeof(a))
30 
31 const double pi = acos(-1.0);
32 const int INF = 0x3f3f3f3f;
33 const int MOD = 1e9 + 7;
34 const double EPS = 1e-9;
35 
36 /*
37 #include <ext/pb_ds/assoc_container.hpp>
38 #include <ext/pb_ds/tree_policy.hpp>
39 
40 using namespace __gnu_pbds;
41 tree<pli, null_type, greater<pli>, rb_tree_tag, tree_order_statistics_node_update> T;
42 */
43 
44 int n, p[200015], vis[200015], deg[200015], par[200015];
45 vector<int> edge[200015];
46 stack<int> sta;
47 vector<int> ans;
48 void dfs2(int x) {
49     ans.pb(x);
50     vis[x] = 1;
51     for (int i = 0; i < edge[x].size(); ++i) {
52         int y = edge[x][i];
53         --deg[y];
54         if (y == par[x]) continue;
55         if (vis[y]) continue;
56         if (deg[y] % 2 == 0) {
57             dfs2(y);
58         }
59     }
60 }
61 void dfs(int p, int x) {
62     sta.push(x);
63     par[x] = p;
64     for (int i = 0; i < edge[x].size(); ++i) {
65         int y = edge[x][i];
66         if (y == p) continue;
67         dfs(x, y);
68     }
69 }
70 int main() {
71     scanf("%d", &n);
72     for (int i = 1; i <= n; ++i) {
73         scanf("%d", &p[i]);
74         if (p[i]) {
75             edge[p[i]].pb(i);
76             edge[i].pb(p[i]);
77             ++deg[p[i]];
78             ++deg[i];
79         }
80     }
81     dfs(0, 1);
82     while (sta.size()) {
83         int x = sta.top(); sta.pop();
84         if (deg[x] % 2 == 0) {
85             dfs2(x);
86         }
87     }
88     if (ans.size() == n) {
89         puts("YES");
90         for (int i = 0; i < ans.size(); ++i) {
91             printf("%d
", ans[i]);
92         }
93     } else {
94         puts("NO");
95     }
96     return 0;
97 }

View Code