Problem Background

JOI Country is a vast nation.

Problem Description

JOI Country has $N$ towns numbered from $1$ to $N$, connected by $N-1$ bidirectional roads.

JOI Country also has $K$ cities numbered from $1$ to $K$, where the $i$-th town belongs to the $C_i$-th city.

Now, the Prime Minister of JOI Country, JOI-kun 114514, wants to select a city as the capital. The capital should be such that any town within the capital can reach another town within the capital without passing through towns outside the capital. This is clearly unreasonable.

Therefore, JOI-kun 114514 plans to merge cities. Merging city $x$ with city $y$ will assign all towns of city $y$ to city $x$.

Determine the minimum number of merges required to establish a capital.

Input Format

The first line contains two integers $N$ and $K$, representing the number of towns and the number of cities, respectively.
The next $N-1$ lines each contain two integers $u$ and $v$, representing a bidirectional road between towns $u$ and $v$.
The following $N$ lines each contain one integer $C_i$, representing that the $i$-th town belongs to the $C_i$-th city.

Output Format

Output a single integer representing the minimum number of merges required.

Sample Input and Output

Sample Input #1

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

Sample Output #1

1

Sample Input #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

Sample Output #2

1

Sample Input #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

Sample Output #3

2

Notes

Sample 1 Explanation

You can merge city $1$ with city $3$, and then choose city $1$ as the capital.

Subtasks

For $100\%$ of the data, $1 \le K, u, v \le N \le 2 \times 10^5$, and it is guaranteed that any town can reach any other town. Additionally, $1 \le C_i \le K$.

Notes

Translated from The 19th Japanese Olympiad in Informatics Spring Training Camp Day4 A Capital City.

见题面 Input 部分

见题面 Output 部分