Chia phe

Quốc gia Zortax bao gồm \(N\) thành phố, được đánh số từ \(1\) đến \(N\), kết nối bởi \(N-1\) con đường hai chiều. Mỗi con đường nối giữa hai thành phố và cho phép di chuyển hai chiều. Toàn bộ hệ thống giao thông tạo thành một mạng lưới liên thông.

Hiện tại, Zortax được chia thành \(K\) vùng, đánh số từ \(1\) đến \(K\). Mỗi thành phố thuộc đúng một vùng. Thành phố thứ \(j\) thuộc vùng \(S_j\) \((1 \le j \le N)\). Mỗi vùng có ít nhất một thành phố.

Tổng thống đương nhiệm -- bà Zelia -- lo ngại rằng đất nước có thể bị chia rẽ bởi mâu thuẫn chính trị giữa các vùng. Zortax được gọi là có nguy cơ ly khai nếu tồn tại cách chia toàn bộ \(N\) thành phố thành hai phe \(X\) và \(Y\) sao cho thỏa mãn tất cả các điều kiện sau:

• Mỗi thành phố thuộc hoặc phe \(X\) hoặc phe \(Y\).
• Cả hai phe đều có ít nhất một thành phố.
• Các thành phố trong cùng một vùng thuộc cùng một phe.
• Có thể di chuyển giữa bất kỳ hai thành phố thuộc phe \(X\) chỉ qua các thành phố thuộc phe \(X\).
• Có thể di chuyển giữa bất kỳ hai thành phố thuộc phe \(Y\) chỉ qua các thành phố thuộc phe \(Y\).

Để đảm bảo sự thống nhất quốc gia, tổng thống Zelia muốn thực hiện các cuộc sáp nhập vùng: mỗi lần, bà chọn hai vùng bất kỳ và gộp lại thành một vùng duy nhất (mọi thành phố của hai vùng sẽ cùng thuộc vùng mới).

Bạn hãy giúp tổng thống tính số lần sáp nhập tối thiểu cần thiết để đảm bảo Zortax không thể ly khai.

Lưu ý: nếu ban đầu chỉ có một vùng (\(K = 1\)), thì quốc gia chắc chắn không thể bị chia rẽ.

\InputFile

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) \((1 \le N \le 5 \times 10^5, 1 \le K \le N)\).
• \(N - 1\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(A_i, B_i\) \((1 \le A_i, B_i \le N)\), biểu diễn một con đường nối hai thành phố.
• \(N\) dòng tiếp theo, dòng thứ \(j\) chứa số \(S_j\) \((1 \le S_j \le K)\) --- mã vùng của thành phố thứ \(j\).

\OutputFile

In ra một số nguyên --- số lần sáp nhập tối thiểu để Zortax không thể bị chia rẽ nữa.

\Scoring

• Subtask 1 (20%): \(N \le 100\), \(K \le 7\)
• Subtask 2 (33%): \(N \le 3000\)
• Subtask 3 (20%): \(N \le 100\,000\), \(K \le 50\)
• Subtask 4 (27%): Không có ràng buộc bổ sung

Example

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

1

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

0