Bài 3: Phá hoại Cầu đường

• Đã thoát ra khỏi Viện Nghiên cứu, nhưng Quân đội Hoàng gia đang bủa vây khắp Vương quốc Alpha. Pitomon quyết định thâm nhập vào hệ thống mạng lưới điều khiển giao thông để đánh sập các cây cầu và tuyến đường, nhằm chia cắt lực lượng truy đuổi.

• Vương quốc Alpha bao gồm \(N\) thành phố và đúng \(N - 1\) tuyến đường hai chiều nối các thành phố (đảm bảo luôn có đường đi duy nhất giữa 2 thành phố bất kỳ). Mỗi thành phố thứ \(i\) chứa một trạm năng lượng với mức năng lượng là \(A_i\).

• Pitomon muốn phá hủy nhiều tuyến đường nhất có thể để chia cắt vương quốc thành các "khu vực" biệt lập. Tuy nhiên, hệ thống tự hủy của vương quốc có một cơ chế phòng ngự cốt lõi: Tổng năng lượng của các thành phố trong mỗi khu vực bị cô lập sau khi chia tách đều phải tự cân bằng, tức là phải là một bội số của số nguyên dương \(K\). Nếu không thỏa mãn, hệ thống an ninh sẽ tự động reset và khôi phục lại toàn bộ.

• Hãy giúp Pitomon tính xem số tuyến đường tối đa có thể bị phá hủy một cách hợp lệ. Nếu không có cách nào thỏa mãn điều kiện, hãy in ra -1.

Input

• Dòng đầu tiên chứa 2 số nguyên \(N\) và \(K\) (\(1 \le N \le 100000\), \(1 \le K \le 10^9\)) mô tả số lượng thành phố và hằng số cân bằng năng lượng.
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) (\(1 \le A_i \le 10^9\)) biểu diễn mức năng lượng của từng thành phố.
• \(N - 1\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên \(u, v\) (\(1 \le u, v \le N\), \(u \neq v\)) mô tả một tuyến đường nối giữa hai thành phố \(u\) và \(v\).

Output

• Một dòng duy nhất chứa 1 số nguyên là số tuyến đường tối đa có thể bị phá hủy một cách hợp lệ. Nếu không thể chia cắt vương quốc theo yêu cầu, in ra -1.

Scoring

• Subtask 1: có 30% số điểm với \(N \le 1000\).
• Subtask 2: có 30% số điểm với \(N \le 100000\); Mạng lưới có dạng một đường thẳng (mỗi thành phố nối với tối đa 2 thành phố khác).
• Subtask 3: có 40% số điểm với \(N \le 100000\); Mạng lưới là một cây tổng quát.

Sample Input 1

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

Sample Output 1

1

Sample Input 2

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

Sample Output 2

-1

Giải thích

Ở ví dụ thứ nhất, tổng năng lượng toàn vương quốc là 1 + 1 + 2 + 1 + 1 = 6 (chia hết cho K = 2). Ta có thể phá hủy tối đa 1 tuyến đường là (2,3). Khi đó vương quốc bị chia thành:

- Khu vực 1 gồm thành phố {1, 2} có tổng năng lượng là 2 (chia hết cho 2).
- Khu vực 2 gồm thành phố {3, 4, 5} có tổng năng lượng là 4 (chia hết cho 2).