JOI 王国共有 $N$ 个城镇，编号为 $1$ 到 $N$。共有 $N-1$ 条道路连接这些城镇。第 $i$ 条道路（$1 \le i \le N-1$）连接城镇 $A_i$ 和城镇 $B_i$。每条道路都可以双向通行。通过这些道路，你可以从任意一个城镇到达其他任何城镇。

目前，JOI 王国被划分为 $K$ 个城市，编号为 $1$ 到 $K$。城镇 $j$（$1 \le j \le N$）属于城市 $C_j$。每个城市至少包含一个城镇。

K 总统是 JOI 王国的国王。他将选择一个城市作为“首都”。出于安全考虑，首都必须满足以下条件：

你可以仅通过属于首都的城镇，从首都内的任意一个城镇到达首都内的其他任何城镇。

然而，K 总统注意到，可能没有任何城市满足此条件，导致他无法选择首都。

为了解决这个问题，K 总统将合并城市。具体来说，他可以执行以下操作：

选择满足 $1 \le x \le K$，$1 \le y \le K$ 且 $x \neq y$ 的 $x$ 和 $y$，将属于城市 $y$ 的所有城镇的所属城市更改为 $x$。

由于合并城市的成本过高，K 总统希望在能够选择任意一个城市作为首都的前提下，最小化合并城市的次数。

请编写一个程序，在给定 JOI 王国的城镇和道路结构以及每个城镇当前所属城市的情况下，计算合并城市的最少次数。

输入格式

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

$N \ K$ $A_1 \ B_1$ $\vdots$ $A_{N-1} \ B_{N-1}$ $C_1$ $\vdots$ $C_N$

输出格式

输出一行到标准输出，表示为了能够选择首都所需合并城市的最少次数。

数据范围

• $1 \le N \le 200\,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 C_j \le K$ ($1 \le j \le N$)
• 对于每个 $k$（$1 \le k \le K$），存在一个整数 $j$（$1 \le j \le N$）使得 $C_j = k$。

子任务

1. (1 分) $N \le 20$
2. (10 分) $N \le 2\,000$
3. (30 分) 每个城镇直接连接的道路不超过两条。
4. (59 分) 无附加限制。

样例

样例输入 1

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

样例输出 1

1

说明 1

在样例 1 中，例如，你可以合并城市 3 和城市 1，选择 $(x, y) = (1, 3)$。然后你可以选择城市 1 作为首都。最初，你无法选择任何城市作为首都。因此，合并城市的最少次数为 1。

样例输入 2

8 4
4 1
1 3
3 6
6 7
7 2
2 5
5 8
2
4
3
1
1
2
3
4

样例输出 2

1

样例输入 3

12 4
7 9
1 3
4 6
2 4
10 12
1 2
2 10
11 1
2 8
5 3
6 7
3
1
1
2
4
3
3
2
2
3
4
4

样例输出 3

2