

Time Limit: 3 sec / Memory Limit: 256 MiB
配点 : 点
問題文
頂点の根つき木が与えられます。 頂点には番号 がついており、根は頂点 です。 そして、頂点 の親は頂点 です。
はじめ、頂点 には整数 が書かれています。 なお、 は の順列になっています。
あなたは以下の操作を 回まで好きな回数実行できます。頂点 に書かれた値が となるようにしてください。
- 頂点を 個選び とする。頂点 と頂点 の間のパスを考える。
- パス上の頂点の値を回転させる。つまり、パス上の各辺 について、頂点 に書かれた値を頂点 に(この操作の直前に)書かれていた値に書き換え、頂点 の値は頂点 に(この操作の直前に)書かれていた値に書き換える。
- なお、頂点 を選んでもよいが、この場合はなにもしないという操作になる。
制約
- は の順列である
入力
入力は以下の形式で標準入力から与えられる。
... ...
出力
行目に操作の回数 を出力せよ。 行目から 行目には、操作で選んだ頂点を順に出力せよ。
入力例 1Copy
5 0 1 2 3 2 4 0 1 3
出力例 1Copy
2 3 4
- 回目の操作後、頂点 に書かれた値は となる
入力例 2Copy
5 0 1 2 2 4 3 1 2 0
出力例 2Copy
3 4 3 1
- 回目の操作後、頂点 に書かれた値は となる
- 回目の操作後、頂点 に書かれた値は となる
Score : points
Problem Statement
You are given a rooted tree with vertices. The vertices are numbered . The root is Vertex , and the parent of Vertex is Vertex .
Initially, an integer is written in Vertex . Here, is a permutation of .
You can execute the following operation at most times. Do it so that the value written in Vertex becomes .
- Choose a vertex and call it . Consider the path connecting Vertex and .
- Rotate the values written on the path. That is, For each edge along the path, replace the value written in Vertex with the value written in Vertex (just before this operation), and replace the value of with the value written in Vertex (just before this operation).
- You may choose Vertex , in which case the operation does nothing.
Constraints
- is a permutation of .
Input
Input is given from Standard Input in the following format:
... ...
Output
In the first line, print the number of operations, . In the second through -th lines, print the chosen vertices in order.
Sample Input 1Copy
5 0 1 2 3 2 4 0 1 3
Sample Output 1Copy
2 3 4
- After the first operation, the values written in Vertex are .
Sample Input 2Copy
5 0 1 2 2 4 3 1 2 0
Sample Output 2Copy
3 4 3 1
- After the first operation, the values written in Vertex are .
- After the second operation, the values written in Vertex are .