JOI 国共有 $N$ 个町，编号为 $1$ 至 $N$。有 $N-1$ 条连接町的道路，第 $i$ 条连接着町 $A_i$ 和町 $B_i$，每条路都可以双向经过。保证町之间可以互相到达。

目前 JOI 国共划分为 $K$ 个城市，第 $i$ 个町属于城市 $C_i$。每个城市拥有至少一个町。

JOI 国国王打算在所有的城市中选出一个城市作为首都，这个城市必须满足:所有属于首都的町可以仅通过属于首都的町互相到达。

但是 JOI 国国王注意到有可能一开始它并不能选出一个满足条件的城市。为了解决这个问题，JOI 国国王打算合并城市。更一般的，每次JOI 国国王会选择两个互不相同城市$x,y$，同时所有归属于城市 $y$ 的町将归属于城市 $x$。

但是因为合并城市的代价较高，因此JOI 国国王想要知道在能选出首都的前提下至少要进行多少次合并操作。

输入格式

第一行两个正整数$N,K$。

接下来$N-1$行，第$i$行两个正整数$A_i,B_i$。

接下来$N$行，第$i$行一个正整数$C_i$。

输出格式

一行一个非负整数表示答案。

样例一

input

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

output

1

explanation

初始并没有可以作为首都的城市。

在合并城市$1,3$后，新城市可以作为首都，因此答案为$1$

样例二

input

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

output

1

样例三

input

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

output

2

数据范围

子任务1($1$分):$N \le 20$

子任务2($10$分):$N \le 2000$

子任务3($30$分):与每个町连接的道路条数不超过2。

子任务4($59$分):无特殊限制。

对于所有测试数据，满足$1 \le K \le N \le 200000,1 \le C_i \le K$。

时间限制:$\texttt{2S}$

空间限制:$\texttt{512MB}$