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.

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.

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.

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.

题意：

给出一棵树，每次可以删除一个度数为偶的点 和 与这个点相连的边。

问是否存在一种方案吧整个树都删除，如果存在，输出任意方案。

题解：

分析：叶节点一定是不能直接删掉的（度数为1），因此要想删掉叶节点，必须先删掉其父节点。

如果父节点的度数为偶，则可以将其删去，

如果父节点的度数为奇，那么要想删掉该父节点，必须先删掉此父节点的父节点………………

是不是有一点向根递归的感觉。

刚才遗漏了很多细节，现在来完善这个思路：

设一个节点的子节点中，度数为奇的子节点数量为cnt[0]，度数为偶的子节点数量为cnt[1]

这个节点的度数deg=cnt[0]+cnt[1]+1

度数为偶的子节点要首先删掉的，那么该节点剩下的度数就是deg-cnt[1]

如果(deg-cnt[1])%2==0，那么这个点也可以直接删掉。

如果(deg-cnt[1])%2==1，那么这个点不能直接删掉，需要先删掉其父节点。

那么一个有意思的树形dp就出来了，v[i]表示将 i 的子节点中能直接删掉的删掉后，i 能否直接删掉（v[i]==0表示不能，v[i]==1表示能）。

最后看v[root]是否为1就可以判断yes，no。

输出方案：

对于一个节点，先删除其子节点中能直接删除的，然后将这个节点删除，这样其不能删除的子节点就可以删除了，将其删除。

递归处理，输出即可。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<ctime>

 #include<cstdlib>

 #include<algorithm>

 #include<cmath>

 #include<string>

 using namespace std;

 int read(){

     int xx=,ff=;char ch=getchar();

     while(ch>''||ch<''){if(ch=='-')ff=-;ch=getchar();}

     while(ch>=''&&ch<=''){xx=xx*+ch-'';ch=getchar();}

     return xx*ff;

 }

 const int maxn=;

 int N,root;

 int lin[maxn],len,deg[maxn];

 struct edge{

     int y,next;

 }e[maxn<<];

 inline void insert(int xx,int yy){

     e[++len].next=lin[xx];

     lin[xx]=len;

     e[len].y=yy;

     deg[xx]++;

 }

 bool v[maxn];//v==1:can delete now,v==0:can not delete now

 int cnt[maxn][];

 bool dfs(int x,int fa){

     for(int i=lin[x];i;i=e[i].next)

         if(e[i].y!=fa)

             cnt[x][dfs(e[i].y,x)]++;

     if((deg[x]-cnt[x][])%==)

         v[x]=;

     else

         v[x]=;

     return v[x];

 }

 void print(int x,int fa){

     for(int i=lin[x];i;i=e[i].next)

         if(e[i].y!=fa)

             if(v[e[i].y])

                 print(e[i].y,x);

     printf("%d\n",x);

     for(int i=lin[x];i;i=e[i].next)

         if(e[i].y!=fa)

             if(!v[e[i].y])

                 print(e[i].y,x);

 }

 int main(){

     //freopen("in.txt","r",stdin);

     N=read();

     for(int i=;i<=N;i++){

         int temp=read();

         if(!temp)

             root=i;

         else

             insert(i,temp),insert(temp,i);

     }

     if(dfs(root,)){

         puts("YES");

         print(root,);

     }

     else

         puts("NO");

     return ;

 }