Goa 王國是一個由 $n$ 個島嶼（編號從 $1$ 到 $n$）組成的網路，這些島嶼由 $n - 1$ 座雙向橋樑連接。該網路的結構為一棵樹。有些島嶼藏有珍貴的寶藏，而 Luffy 正踏上尋找所有島嶼寶藏的旅程。

為了簡化尋寶過程，他從當地商人那裡買了一個探測器。該探測器本應顯示每個島嶼到最近寶藏的距離（以橋樑數量計算）；然而，它似乎壞得很嚴重，反而顯示了每個島嶼到最遠寶藏的距離！

儘管如此，他還是保留了壞掉的探測器為每個島嶼顯示的距離，希望或許並非一切都已失去。他現在想知道哪些島嶼更有可能藏有寶藏。

你的任務是幫助 Luffy 將這 $n$ 個島嶼按包含寶藏的機率從高到低進行排序，已知他現在掌握了探測器為每個島嶼顯示的距離。最初，你可以假設每個島嶼獨立地有 $50\%$ 的機率包含寶藏；換句話說，每個島嶼的子集作為寶藏島嶼子集的機率是相等的。

輸入格式

第一行包含一個整數 $n$ ($1 \le n \le 250\,000$)，代表島嶼的數量。接下來的 $n - 1$ 行描述了橋樑。每座橋樑連接兩個不同的島嶼。最後一行包含 $n$ 個非負整數，代表 Luffy 的探測器為每個島嶼顯示的距離（以橋樑數量計算）。

保證至少存在一個與輸入資料一致的非空子集。

輸出格式

輸出一個大小為 $n$ 的排列，即島嶼按包含寶藏的機率從高到低排序的順序。如果兩個島嶼包含寶藏的機率相同，則按它們編號的升序輸出。

範例

輸入 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$ 是唯一包含寶藏的島嶼。