Silvermill 最近预算紧张，市长 Peanut 打算拆除一些道路以节省维护成本。Silvermill 可以描述为一个拥有 $N$ 个路口和 $E$ 条连接它们的道路的城市，其中第 $i$ 条道路连接路口 $A_i$ 和 $B_i$。每个路口编号为 $1, \dots, N$，每条道路编号为 $1, \dots, E$。保证任意两个路口之间都可以直接或间接地到达，且没有两条道路共享相同的端点。
为了推进这项工作，Peanut 雇佣你来帮助评估道路的维护成本。Peanut 的任务如下：你需要报告一个列表 $W = (W_1, W_2, \dots, W_E)$，使得 $W$ 是 $1, \dots, E$ 的一个排列，且 $W_i$ 是保留第 $i$ 条道路的成本。
随后，Peanut 将选择一个道路子集进行保留，使得：
- 所有路口保持连通。
- 所保留道路的成本之和最小。
换句话说，Peanut 将根据你给出的权重保留最小生成树。注意，由于成本各不相同，最小生成树是唯一的。
Peanut 不知道的是，你有一个隐藏的议程。你希望保留一个构成生成树的道路子集 $R$。请注意，你可以通过仔细选择 $W$ 来诱导 Peanut 选择 $R$。你的目标是找到满足上述条件的字典序最小的排列 $W$。
总之，给定一个构成生成树的道路子集 $R$，找到字典序最小的权重分配 $W$，使得该城市的最小生成树为 $R$。
输入格式
你的程序必须从标准输入读取数据。
输入的第一行包含两个整数 $N$ 和 $E$。
接下来 $E$ 行，第 $i$ 行包含两个整数 $A_i$ 和 $B_i$，描述一条道路。
输入的最后一行包含 $N - 1$ 个整数，即你希望保留的道路集合 $R$ 中的道路编号。
输出格式
你的程序必须输出到标准输出。
输出应包含一行 $E$ 个整数，即导致 $R$ 被选为最小生成树的字典序最小的排列 $W$。
子任务
每个实例的最大执行时间为 2.0 秒。对于所有测试用例，输入满足以下范围：
- $1 \le N, E \le 3 \times 10^5$
- $1 \le A_i \neq B_i \le N$
- $1 \le R_i \le N$
- 仅使用 $R$ 中的道路即可在任意两个路口之间通行。
你的程序将在满足以下限制的输入实例上进行测试：
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 8 | $1 \le N, E \le 9$ |
| 2 | 19 | $1 \le N, E \le 10^3$ |
| 3 | 9 | $A_{R_i} = 1, B_{R_i} = i + 1$，即 $R$ 是一颗星形树。 |
| 4 | 10 | $A_{R_i} = i, B_{R_i} = i + 1$，即 $R$ 是一条链。 |
| 5 | 10 | $E = N, A_i = i, B_i = i \pmod N + 1$ |
| 6 | 12 | $E = N$ |
| 7 | 32 | - |
样例
样例输入 1
4 5 3 4 1 2 2 3 1 3 1 4 2 4 5
样例输出 1
3 4 5 1 2
说明 1
上图显示了道路和路口（见输入）。边上的数字是你分配的权重（见输出）。高亮显示的道路被 Peanut 选中，这等同于输入中的 $R$。因此，输出是正确的。
样例输入 2
4 4 1 2 1 4 2 3 3 4 1 3 4
样例输出 2
1 4 2 3
说明 2
