F - Coins on the tree

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

高橋君は、N 頂点から成る根付き木上で、M 枚のコインを使って以下の操作をちょうど K 回行おうとしています。

この木は、頂点 i の親が p_i であるものとして与えられます。p_i = 0 である頂点が根です。

各操作では、

  • 根にコインが置かれていない場合に、根に新しいコインを置く

もしくは

  • コインの置かれている頂点を 1 つ選んで、コインの置かれていない子のどれかにコインを移動する

のどちらかを行うことができます。

K 回の操作のあと、M枚 のコイン全てが木のどこかに置かれていなければなりません。

1 枚目に根に置いたコイン, 2 枚目に根に置いたコイン, ..., M 枚目に根に置いたコイン の置かれている頂点を v_1, v_2, ..., v_M とします。

高橋君は、この列 v_1, v_2, ..., v_M のうち、辞書順で最小であるものが知りたくなりました。

高橋君のためにこの列を求めてあげてください。

u_1, u_2, ..., u_M が 列 v_1, v_2, ..., v_M より辞書順で小さいとは、u_i < v_i かつ 、全ての j < iu_j = v_j が成り立つような 1 \leq i \leq M が存在する場合を言います。

ただし、ちょうど K 回の操作を行えない場合や、M 枚のコインを木に置けない場合は、-1 を出力してください。

制約

  • 1 \leq M \leq N \leq 300
  • 0 \leq K \leq 10^5
  • 0 \leq p_i \leq N
  • p_i = 0 となる i はただ 1 つ存在する
  • (i, p_i) に辺を張ってできるグラフは木を成す
  • 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N M K
p_1 p_2 ... p_{N-1} p_N

出力

K 回の操作後、M 枚のコインが全て置かれているように出来る場合は、

v_1 v_2 ... v_{M-1} v_M

のように、不可能な場合は -1 を出力せよ。


入力例 1

3 2 4
2 0 2

出力例 1

1 3

次ののように操作を行うことで \{1, 3\} の列を作ることができ、これより辞書順で小さい列を作ることはできません。

  • 1 枚目のコインを頂点 2 に置く

操作1

  • 1 枚目のコインを頂点 2 から 1 に動かす

操作2

  • 2 枚目のコインを頂点 2 に置く

操作3

  • 2 枚目のコインを頂点 2 から 3 に動かす

操作4

上の画像では、1 枚目のコインを赤、2 枚目のコインを青で表しています。


入力例 2

3 2 5
2 0 2

出力例 2

-1

5 回の操作を行うことが出来ないので、 -1 を出力してください。