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

说明 1

在第一个样例中，岛屿 3 必须包含宝藏，因为它是唯一一个距离岛屿 2 为 2 的岛屿。岛屿 4 和 5 包含宝藏的概率均为 $2/3$，而岛屿 1 和 2 的概率为 $1/2$。

输入格式 2

4
2 1
3 2
3 4
1 0 1 2

输出格式 2

2 1 3 4

说明 2

在第二个样例中，唯一可能的方案是岛屿 2 是唯一包含宝藏的岛屿。