JOI 联合国有 $N$ 座城市，编号为 $1$ 到 $N$，以及 $N-1$ 条公路，编号为 $1$ 到 $N-1$。第 $i$ 条公路 ($1 \le i \le N-1$) 连接城市 $A_i$ 和城市 $B_i$，且是双向的。通过这些公路，可以在任意两座城市之间通行。

目前，JOI 联合国有 $K$ 个州，编号为 $1$ 到 $K$。城市 $j$ ($1 \le j \le N$) 属于州 $S_j$。每个州至少包含一座城市。

JOI 联合国的总统 K 先生担心国家分裂。如果可以将所有城市划分为 X 组和 Y 组，并满足以下条件，则称 JOI 联合国是“可分离的”：

• 每座城市都属于 X 组或 Y 组。
• X 组至少包含一座城市。
• Y 组至少包含一座城市。
• 对于任何一个州，该州的所有城市都属于同一个组。
• X 组内的任意两座城市都可以仅通过属于 X 组的城市和公路相互到达。
• Y 组内的任意两座城市都可以仅通过属于 Y 组的城市和公路相互到达。

K 先生打算通过合并州来使 JOI 联合国变得不可分离。当他合并州时，他会选择两个州并将它们统一为一个州。统一后的州包含原先两个州的所有城市。K 先生希望通过最少次数的合并，使 JOI 联合国变得不可分离。

注意，如果 JOI 联合国只有一个州，则它是不可分离的。

请编写一个程序，在给定城市、公路和州的信息后，计算使 JOI 联合国变得不可分离所需的最少合并次数。

输入格式

从标准输入读取以下数据。所有输入值均为整数。

$N \ K$ $A_1 \ B_1$ $:$ $A_{N-1} \ B_{N-1}$ $S_1$ $:$ $S_N$

输出格式

输出使 JOI 联合国变得不可分离所需的最少合并次数。

数据范围

• $1 \le N \le 500\,000$
• $1 \le K \le N$
• $1 \le A_i \le N$ ($1 \le i \le N-1$)
• $1 \le B_i \le N$ ($1 \le i \le N-1$)
• 可以通过公路在任意两座城市之间通行。
• $1 \le S_j \le K$ ($1 \le j \le N$)
• 对于任意 $k$ ($1 \le k \le K$)，存在 $j$ ($1 \le j \le N$) 使得 $S_j = k$。

子任务

1. (10 分) $N \le 100, K \le 7$
2. (24 分) $N \le 3\,000$
3. (14 分) $N \le 100\,000, K \le 50$
4. (22 分) $N \le 100\,000$。在初始情况下，属于同一个州的任意两座城市之间最多经过 $100$ 条公路即可到达。
5. (30 分) 无附加限制。

样例

样例输入 1

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

样例输出 1

1

说明 1

在此样例中，初始情况下 JOI 联合国是可分离的。例如，如果将城市 1、2、3 和 4 分为 X 组，将城市 5 分为 Y 组，则满足可分离的条件。 如果 K 先生合并州 3 和州 4，JOI 联合国将变得不可分离。因此答案为 1。

样例输入 2

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

样例输出 2

0

说明 2

在此样例中，初始情况下 JOI 联合国是不可分离的。因此答案为 0。

样例输入 3

2 2
1 2
1
2

样例输出 3

1