题目内容

某公司共有 $n$ 名员工，编号为 $1$ 到 $n$，CEO 的编号为 $1$。员工之间的管理关系构成一个树形结构，共有 $n-1$ 条直接汇报关系。初始时，第 $i$ 名员工的绩效分为 $a_i = i$。

公司接下来要进行 $m$ 轮绩效评优。在第 $j$ 轮（$1 \le j \le m$）中，会指定一名员工 $x$，并从员工 $x$ 及其所有直接或间接下属中，找出当前绩效分最低的那名员工，随后将该员工的绩效分更新为 $n + j$。

请你求出所有评优结束后，每名员工的最终绩效分。

数据范围：员工数量 $n$ 和评优轮次 $m$ 均满足 $2 \le n, m \le 10^5$。所有直接汇报关系给出的员工编号 $u_i, v_i$ 满足 $1 \le u_i, v_i \le n$ 且 $u_i e v_i$，保证构成一棵以 $1$ 为根的树。每次指定的员工 $x$ 满足 $1 \le x \le n$。

输入描述

第一行包含两个整数 $n$ 和 $m$，表示员工数量和评优轮次。 接下来 $n-1$ 行，每行两个整数 $u$ 和 $v$，表示一条直接管理关系（双向关系，保证整体形成一棵以 $1$ 为根的树）。 随后 $m$ 行，每行一个整数 $x$，依次表示每轮评优指定的员工编号。

输出描述

输出一行 $n$ 个整数，依次表示员工 $1$ 到员工 $n$ 的最终绩效分，整数之间用一个空格分隔。

样例1

输入

4 3
1 2
1 3
2 4
1
2
3

输出

5 6 7 4

说明

初始时员工绩效分为 $a_1=1$, $a_2=2$, $a_3=3$, $a_4=4$。

第 1 轮指定员工 1，其子树包含节点 1,2,3,4，当前绩效中最小值为 1（员工 1），将其更新为 $n+1=5$。

第 2 轮指定员工 2，其子树包含节点 2,4，当前绩效分别为 2,4，最小值为 2（员工 2），更新为 $n+2=6$。

第 3 轮指定员工 3，其子树仅包含节点 3，当前绩效为 3，更新为 $n+3=7$。

员工 4 从未被更新，绩效保持为 4。最终绩效依次为 5 6 7 4。

样例2

输入

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

输出

6 7 3 4 5

说明

初始 $a_i=i$（$i=1\dots 5$）。

第 1 轮指定员工 1，其子树包含全部员工 1,2,3,4,5，最小绩效为 1（员工 1），更新为 $n+1=6$。

第 2 轮指定员工 2，其子树包含 2,4,5，当前绩效为 2,4,5，最小值为 2（员工 2），更新为 $n+2=7$。

员工 3,4,5 未被修改，保持原值。最终结果为 6 7 3 4 5。

样例3

输入

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

输出

8 7 9 4 5 6

说明

初始 $a_i=i$。

第 1 轮指定 2，子树包含 2,3,4，最小绩效 2（员工 2），更新为 $n+1=7$。

第 2 轮指定 1，子树包含全部，当前最小为 1（员工 1），更新为 $n+2=8$。

第 3 轮指定 3，子树包含 3,4，当前绩效 3,4，最小 3（员工 3），更新为 $n+3=9$。

最终输出 8 7 9 4 5 6。