题目描述

你有一棵包含 $n$ 个节点的树。初始时，每个节点上都有一枚宝石。

你依次对这棵树执行 $q$ 次操作。第 $i$ 次操作如下：

1. 选择一个节点 $x_i$，并将整棵树以 $x_i$ 为根；
2. 对于每个节点 $u$，将当前位于 $u$ 上的所有宝石移动到其父节点 $\mathrm{fa}_u$ 上；
3. 若 $u=x_i$，即 $u$ 是当前的根节点，则该节点上的宝石不移动。

求完成全部操作后，每一枚宝石最终所在的节点。

输入格式

第一行包含两个整数 $n,q$，分别表示节点数和操作数。

接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示树上存在一条连接节点 $u$ 和节点 $v$ 的边。

接下来一行包含 $q$ 个整数

表示操作序列。

输出格式

输出 $n$ 个整数。第 $i$ 个整数 $a_i$ 表示初始位于节点 $i$ 上的宝石最终所在的节点。

样例 1

输入

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

输出

2 4 2 2 2

数据范围与约定

• 对于 $10\%$ 的数据：

  $$n,q\le 100.$$

• 对于 $20\%$ 的数据：

  $$n\le 1000.$$

• 对于额外 $20\%$ 的数据：

  $$n,q\le 50000,\qquad x_i\le 8.$$

• 对于全部测试数据：

  $$1\le n,q\le 200000.$$

最后一部分数据在区间 $[100000,200000]$ 内具有梯度。