Hợp chúng quốc JOI có \(N\) thành phố, được đánh số từ \(1\) đến \(N\), và \(N-1\) đường cao tốc hai chiều, được đánh số từ \(1\) đến \(N-1\). Đường cao tốc thứ \(i\) nối hai thành phố \(A_i\) và \(B_i\). Có thể đi từ một thành phố bất kỳ đến bất kỳ thành phố nào khác bằng các đường cao tốc.

Đất nước có \(K\) bang, được đánh số từ \(1\) đến \(K\). Thành phố thứ \(j\) thuộc bang \(S_j\). Mỗi bang có ít nhất một thành phố.

Đất nước được gọi là có thể chia tách nếu có thể chia toàn bộ các thành phố thành hai nhóm \(X\) và \(Y\) thỏa mãn tất cả các điều kiện sau:

1. Mỗi thành phố thuộc đúng một trong hai nhóm \(X\) và \(Y\).
2. Nhóm \(X\) có ít nhất một thành phố.
3. Nhóm \(Y\) có ít nhất một thành phố.
4. Với mỗi bang, tất cả các thành phố của bang đó thuộc cùng một nhóm.
5. Có thể đi giữa hai thành phố bất kỳ của nhóm \(X\) bằng các đường cao tốc mà chỉ đi qua các thành phố thuộc nhóm \(X\).
6. Có thể đi giữa hai thành phố bất kỳ của nhóm \(Y\) bằng các đường cao tốc mà chỉ đi qua các thành phố thuộc nhóm \(Y\).

Tổng thống K muốn làm cho đất nước không thể chia tách. Để thực hiện điều này, ông có thể tiến hành sáp nhập các bang. Trong một lần sáp nhập, ông chọn hai bang và gộp tất cả các thành phố của hai bang đó thành một bang.

Hãy tính số lần sáp nhập ít nhất để đất nước không thể chia tách. Lưu ý rằng một đất nước chỉ có một bang thì không thể chia tách.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N K
A_1 B_1
...
A_{N-1} B_{N-1}
S_1
...
S_N

Dữ liệu ra

In ra một dòng chứa một số nguyên: số lần sáp nhập ít nhất để đất nước không thể chia tách.

Ràng buộc

• \(1 \le N \le 500\,000\).
• \(1 \le K \le N\).
• \(1 \le A_i,B_i \le N\) với \(1 \le i \le N-1\).
• Có thể đi giữa hai thành phố bất kỳ bằng các đường cao tốc.
• \(1 \le S_j \le K\) với \(1 \le j \le N\).
• Với mỗi \(k\) thỏa mãn \(1 \le k \le K\), tồn tại ít nhất một \(j\) sao cho \(S_j=k\).
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(10\) điểm: \(N \le 100\), \(K \le 7\).
2. \(24\) điểm: \(N \le 3\,000\).
3. \(14\) điểm: \(N \le 100\,000\), \(K \le 50\).
4. \(22\) điểm: \(N \le 100\,000\). Ban đầu, có thể đi giữa hai thành phố bất kỳ thuộc cùng một bang bằng một đường đi sử dụng không quá \(100\) đường cao tốc.
5. \(30\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

2 2
1 2
1
2

1

Nguồn

JOI 2018/2019, trại huấn luyện mùa xuân, ngày thi thứ 4 (23/03/2019). Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản. Trang công bố cấp phép nội dung theo CC BY-SA 4.0; bản dịch giữ cùng giấy phép.