Goa王国は $n$ 個の島（$1$ から $n$ までの番号が付けられている）からなるネットワークで、それらは $n - 1$ 本の双方向の橋で結ばれています。このネットワークは木構造をしています。いくつかの島には貴重な宝物が隠されており、ルフィはすべての島から宝物を見つける冒険に出ています。

宝探しを楽にするために、彼は地元の商人から探知機を購入しました。本来、この探知機は各島から最も近い宝物までの距離（橋の数）を表示するはずでしたが、ひどく故障しているようで、代わりに各島から最も遠い宝物までの距離を表示してしまいます！

それにもかかわらず、彼は故障した探知機が各島について示した距離を記録しており、すべてが失われたわけではないと期待しています。彼は今、探知機が示した各島の距離を知った上で、どの島が宝物を含んでいる可能性が高いのかを知りたがっています。

あなたの仕事は、各島が宝物を含んでいる確率が高い順に $n$ 個の島を並べ替えることで、ルフィを助けることです。初期状態として、各島は独立して $50\%$ の確率で宝物を含んでいると仮定できます。言い換えれば、宝物がある島の集合として、すべての島の部分集合が等確率で選ばれるということです。

入力

入力の最初の行には、島の数 $n$ ($1 \le n \le 250\,000$) が含まれます。続く $n - 1$ 行は橋を表します。各橋は2つの異なる島を結んでいます。最後に、最後の行には各島についてルフィの探知機が示した距離（橋の数）を表す $n$ 個の非負整数が含まれます。

入力データと矛盾しない空でない部分集合が少なくとも1つ存在することが保証されています。

出力

宝物を含んでいる確率が高い順に島を並べた $n$ 個の順列を出力してください。2つの島の宝物を含む確率が同じ場合は、IDの昇順に出力してください。

入出力例

入力 1

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

出力 1

3 4 5 1 2

入力 2

4
2 1
3 2
3 4
1 0 1 2

出力 2

2 1 3 4

注記

最初の例では、島 3 は島 2 から距離 2 にある唯一の島であるため、宝物を含んでいる必要があります。島 4 と島 5 はそれぞれ $2/3$ の確率を持ち、島 1 と島 2 はそれぞれ $1/2$ の確率を持ちます。

2番目の例では、唯一可能なシナリオは、島 2 だけが宝物を含んでいる場合です。