実行時間制限: 2 sec / メモリ制限: 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 < i で u_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 枚目のコインを頂点 2 から 1 に動かす
- 2 枚目のコインを頂点 2 に置く
- 2 枚目のコインを頂点 2 から 3 に動かす
上の画像では、1 枚目のコインを赤、2 枚目のコインを青で表しています。
入力例 2
3 2 5 2 0 2
出力例 2
-1
5 回の操作を行うことが出来ないので、 -1 を出力してください。