Capital City Merging

JOI Kingdom has N towns (numbered from 1 to N) connected by N-1 bidirectional roads, forming a tree. The kingdom also has K cities (numbered from 1 to K), and the i-th town belongs to city C_i.

The Prime Minister, JOI-kun 114514th, wants to choose one city as the capital. However, a capital must satisfy the following condition: for any two towns in that capital, there must exist a path connecting them that goes only through towns of that same capital. In other words, the set of towns of the capital must form a connected subtree of the tree.

It is observed that with the current arrangement many cities do not form connected subtrees. To remedy this, JOI-kun is allowed to merge two cities. When city x is merged with city y, all towns belonging to city y become part of city x (their city label is changed to x).

Your task is to determine the minimum number of merge operations required so that there exists at least one city (the eventual capital) whose towns form a connected subtree.

More formally: Given a tree T with N nodes and an assignment of initial colors (cities) C_1, C_2, \dots, C_N, you are allowed to perform operations of the form: choose two distinct cities x and y and change every occurrence of y to x. Find the minimum number of such merge operations needed so that in the resulting coloring, there exists at least one color X for which the set of nodes with color X is connected in T.

Note: Any formula appearing in this statement is rendered in \( \LaTeX \) format. For example, the number of towns is \(N\) and the number of roads is \(N-1\).

inputFormat

The input is given in the following format:

N K
u1 v1
u2 v2
... (N-1 lines of roads)
C1 C2 ... CN

where:

• N is the number of towns.
• K is the number of cities.
• Each of the next N-1 lines contains two integers u and v representing a bidirectional road connecting towns u and v.
• The last line contains N integers where the i-th integer is C_i, the city to which town i belongs.

outputFormat

Output a single integer — the minimum number of merge operations required so that there exists a city whose towns form a connected subtree.

sample

3 2
1 2
2 3
1 2 1

0