Description

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

JOI Country also has $K$ cities, numbered from $1$ to $K$. Town $i$ belongs to city $C_i$.

Now the Prime Minister of JOI Country, Mr. JOI the $114514$th, wants to choose one city as the capital. The city chosen as the capital must satisfy the following condition: from any town in the capital to any other town in the capital, it is possible to travel using only towns in the capital. However, there may be no city that satisfies this condition.

Therefore, Mr. JOI the $114514$th will perform city merges. Merging city $x$ and city $y$ will move all towns in city $y$ into city $x$.

Find the minimum number of merges needed so that a capital can be chosen.

Input Format

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

Output Format

Output one integer in a single line, representing the minimum number of merges.

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

1

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

1

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

2

Hint

Explanation for Sample 1

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

Subtasks

Constraints

For $100\%$ of the testdata, $1 \le K, u, v \le N \le 2 \times 10^5$. It is guaranteed that starting from any town you can reach all other towns. Also, $1 \le C_i \le K$.

Notes

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

Translated by ChatGPT 5