木の上の生活 (tree)

小忆（シャオイー）と小艾（シャオアイ）は木の上に住んでいます。この木 $T$ は $n$ 個の頂点と $n - 1$ 本の辺からなります。今、木の上に順列 $p$ があります。小艾は毎回、辺 $(u, v) \in T$ を一つ選び、$p_u$ と $p_v$ を入れ替えることができます。小艾のタスクは、この順列をソートすることです。小艾は、最低何回の交換が必要かを推定するために小忆に相談しました。小忆は考えた末に、次の式を書き出しました。

$$\frac{1}{2} \sum_{i=1}^{n} \text{dist}(i, p_i)$$

小艾が試してみたところ、偶然にも現在の順列が小忆の示した下界にちょうど一致していることが分かりました！彼はあなたに、この下界を達成するソート手順を提示できるか尋ねています。特に、彼は提示する手順の辞書順が最小になることを望んでいます。木の辺には $1$ から $n - 1$ までの番号が付けられており、手順の辞書順は、操作する辺の番号を順に比較することで決定されます。

問題文

木 $T$ と順列 $p$ が与えられます。辺の交換操作を繰り返して順列をソートしてください。操作回数は $\frac{1}{2} \sum_{i=1}^{n} \text{dist}(i, p_i)$ 回である必要があります。この条件を満たす手順のうち、操作する辺の番号列が辞書順最小となるものを求めてください。

入力形式

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

$n$ $u_1 \ v_1$ $u_2 \ v_2$ $\vdots$ $u_{n-1} \ v_{n-1}$ $p_1 \ p_2 \ \dots \ p_n$

出力形式

辞書順最小の解における、操作する辺の番号を順に空白区切りで出力せよ。

サンプル

サンプル 1

5
5 2
3 2
2 4
1 3
2 1 5 3 4

2 1 3 4 2

注記

初期状態は $2, 1, 5, 3, 4$ です。以下の $5$ 回の操作により、順列は次のように変化します。

• $2, 5, 1, 3, 4$
• $2, 4, 1, 3, 5$
• $2, 3, 1, 4, 5$
• $1, 3, 2, 4, 5$
• $1, 2, 3, 4, 5$

サンプル 2

選手ディレクトリ内の tree/tree2.in および tree/tree2.ans を参照してください。

制約

すべてのデータにおいて、$1 \le n \le 10^3$ を満たし、与えられた順列は $\frac{1}{2} \sum_{i=1}^{n} \text{dist}(i, p_i)$ 回の操作でソート可能であることが保証されている。

特殊制約：

• A: 辺集合が $\{(1, 2), (2, 3), \dots, (n - 1, n)\}$ である。
• B: 辺集合が $\{(1, 2), (1, 3), \dots, (1, n)\}$ である。
• 0: 辺が前述の順序通りに与えられることが保証されている。
• 1: 辺が任意の順序で与えられる可能性がある。

サブタスク

この問題にはサブタスクの設定はありません。