Vương quốc JOI có \(N\) thị trấn, đánh số từ \(1\) đến \(N\). Có \(N-1\) con đường nối các thị trấn. Đường thứ \(i\) (\(1 \le i \le N-1\)) nối thị trấn \(A_i\) và thị trấn \(B_i\), đi được theo cả hai chiều. Có thể đi từ bất kỳ thị trấn nào đến bất kỳ thị trấn nào khác qua các con đường.

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

Ngài K là vua của vương quốc JOI. Ngài muốn chọn một thành phố làm thủ đô. Vì lý do an ninh, thủ đô phải thỏa mãn điều kiện: có thể đi từ bất kỳ thị trấn nào thuộc thủ đô đến bất kỳ thị trấn nào khác thuộc thủ đô mà chỉ đi qua các thị trấn thuộc thủ đô.

Tuy nhiên, có thể không thành phố nào thỏa mãn điều kiện đó. Để giải quyết vấn đề, ngài K sẽ sáp nhập các thành phố bằng thao tác sau:

Chọn \(x,y\) thỏa mãn \(1 \le x,y \le K\) và \(x\ne y\), rồi chuyển tất cả thị trấn đang thuộc thành phố \(y\) sang thành phố \(x\).

Vì sáp nhập rất tốn kém, ngài K muốn thực hiện ít lần sáp nhập nhất để có thể chọn một thành phố làm thủ đô. Cho cấu trúc các thị trấn, các con đường và thành phố mà mỗi thị trấn đang thuộc về, hãy tính số lần sáp nhập nhỏ nhất.

Dữ liệu vào

Đọc từ đầu vào chuẩn. Tất cả giá trị đều là số nguyên, theo định dạng:

N K
A_1 B_1
...
A_{N-1} B_{N-1}
C_1
...
C_N

Dữ liệu ra

In ra một dòng chứa số lần sáp nhập thành phố ít nhất cần thực hiện để có thể chọn thủ đô.

Ràng buộc

• \(1 \le N \le 200\,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 từ bất kỳ thị trấn nào đến bất kỳ thị trấn nào khác qua các con đường.
• \(1 \le C_j \le K\) với \(1 \le j \le N\).
• Với mỗi \(1 \le k \le K\), tồn tại ít nhất một \(j\) (\(1 \le j \le N\)) sao cho \(C_j=k\).

Phân nhóm

Các ràng buộc chung áp dụng cho mọi nhóm.

1. \(1\) điểm: \(N \le 20\)
2. \(10\) điểm: \(N \le 2000\)
3. \(30\) điểm: Mỗi thị trấn được nối trực tiếp bằng đường với nhiều nhất hai thị trấn khác
4. \(59\) điểm: Không có

Ví dụ

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

Nguồn

JOI 2019/2020, Trại huấn luyện mùa xuân, ngày thi 4. Đề gốc của Ủy ban Olympic Tin học Nhật Bản, được cung cấp theo giấy phép CC BY-SA 4.0. Bản tiếng Việt được dịch từ đề tiếng Anh chính thức.