AT_joisc2019_k.合併 (Mergers)

JOI 合众国有 $N$ 个城市，编号为 $1\dots N$，并且有 $N−1$ 条高速公路，编号为 $1\dots N−1$。第 $i (1\le i\le N−1)$ 条高速公路双向连接城市 $A_i$ 与 $B_i$。一个人可以利用高速公路从任意一个城市到达另一个城市。

目前，JOI 合众国有 $K$ 个州，编号为 $1\dots K$，城市 $j (1\le j\le N)$ 属于州 $S_j$。任意一个州内至少有一个城市。

JOI 合众国总统 K 先生害怕国家会分裂。JOI 合众国被称作可分裂的当且仅当所有城市可以被划分为 $\texttt X$ 组和 $\texttt Y$ 组，并且满足以下条件：

• 所有城市属于 $\texttt X$ 组或 $\texttt Y$ 组之一；
• $\texttt X$ 组中至少有一个城市；
• $\texttt Y$ 组中至少有一个城市；
• 对于任意一个州，所有所属州相同的城市都在同一组；
• 一个人可以从 $\texttt X$ 组的任意一个城市出发，通过高速公路且只经过 $\texttt X$ 组的城市到达 $\texttt X$ 组的任意一个城市；
• 一个人可以从 $\texttt Y$ 组的任意一个城市出发，通过高速公路且只经过 $\texttt Y$ 组的城市到达 $\texttt Y$ 组的任意一个城市。

K 先生将要合并一些州，使得 JOI 合众国是不可分裂的。当他合并州的时候，他会选择两个州，然后把这两个州合并成一个新州。新州下辖的城市为原来两个州所有下辖的城市。K 先生想要在合并次数最少的情况下完成合并任务，使得 JOI 合众国是不可分裂的。

注意，如果 JOI 合众国只有一个州，那么它是不可分裂的。

写一个程序，在给定所有城市，州和高速公路的信息的情况下，计算使得 JOI 合众国不可分裂的最小合并次数。

第一行两个正整数 $N,K$，表示城市数量和洲的数量。

接下来 $N-1$ 行每行两个正整数 $A_i,B_i$，表示一条高速公路。

接下来 $N$ 行每行一个数 $S_j$，表示第 $j$ 个城市属于第 $S_j$ 个洲。

输出一行一个整数，表示使得 JOI 合众国不可分裂的最小合并次数。

输入输出样例

样例输入 #1

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

样例输出 #1

1

样例输入 #2

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

样例输出 #2

0

样例输入 #3

2 2
1 2
1
2

样例输出 #3

1

说明/提示

【样例解释】

对于第一组样例，最初国家是可分裂的。例如，将城市 $1,2,3,4$ 归为 $\texttt X$ 组，将城市 $5$ 归为 $\texttt Y$ 组。如果将第 $3$ 个洲和第 $4$ 个洲合并，国家就会变得不可分裂。因此答案是 $1$。

对于第二组样例，最初国家是不可分裂。因此答案是 $0$。

【数据范围】

对于 $100\%$ 的数据，$1\le N\le 5\times 10^5,1\le K,A_i,B_i\le N,1\le S_i\le K$。