Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Để có thể thích nghi và hòa nhập với những cư dân bản địa của hành tinh E, JM đã phải luyện tập rất nhiều. Một trong những bài luyện tập của cô thuộc về khả năng tính toán, và thực hiện trên một hệ thống siêu máy tính mô phỏng như sau:

Trên hệ thống mô phỏng là một hệ thống đền và đường nối. Hệ thống này có thể được coi như một cây, tức là giữa 2 ngôi đền bất kỳ trong hệ thống chỉ có 1 con đường di duy nhất nối chúng.

Trong các ngôi đền, có những ngôi đền không đánh số, có những ngôi đền được đánh những con số - không rõ ý nghĩa của chúng là gì, nhưng có một đặc điểm chung: đó đều là các số nguyên dương.

JM đang đứng ở đền chủ, được đánh số thứ tự là 1, và trên bức tường của đền này có 2 con số M và Z. Nhiệm vụ của cô là thu thập những mảnh cổ vật trong hệ thống đền này.

Để đảm bảo bí mật về sức mạnh tiềm tàng của khu đền, những mảnh cổ vật được che đậy rất kỹ lưỡng, và được đặt ở rất sâu: chỉ những đền ngách (là những ngôi đền không phải đền chủ, và chỉ kết nối với 1 ngôi đền khác) là chứa những mảnh bảo bối này.

Dĩ nhiên, việc lấy chúng ra khỏi đền không khó gì với năng lực hủy diệt của JM. Nhưng có một vấn đề khác rắc rối hơn: con đường cô đi từ đền chủ tới đền ngách phải thỏa mãn 1 trong 2 điều kiện sau:

•           Không đi qua bất kỳ ngôi đền nào có đánh số.

•           Nếu cô đi qua ít nhất 1 ngôi đền đánh số, thì tích tất cả các số trên các ngôi đền đó chia lấy dư cho M không được vượt quá giá trị Z.

Nếu không điều kiện nào thỏa mãn, toàn bộ năng lượng của khu đền sẽ phóng thích và giam chặt cô lại dưới lớp gạch của khu đền, như một sự trừng phạt về thói cẩu thả và thiếu tính toán.

Mỗi lần lấy một mảnh cổ vật, JM sẽ xuất phát từ đền gốc, tới đền ngách mà cô lựa chọn, và nếu có thể lấy được bảo vật an toàn, cô phải trở về đền gốc để thực hiện nghi lễ và chuẩn bị cho lần di chuyển sang đền ngách tiếp theo.

Qua hàng nghìn lần tập luyện, và không thiếu những lần sơ suất kẹt lại dưới đáy đất, cộng thêm tốc độ tính toán chớp nhoáng của mình, giờ đây JM có thể tự tin vạch ra trong 2s toàn bộ lộ trình di chuyển sao cho cô có thể lấy được nhiều mảnh cổ vật nhất, mà không bị giam cầm dưới chân đền.

Và giờ, cô ta chuyển thử thách này tới cho bạn.

Bạn có dám chấp nhận thử thách của JM?

Input

Dòng đầu tiên chứa 3 số N, M, Z (2 <= N <= 10^5, 0 <= Z < M <= 10^9+7), lần lượt là số ngôi đền trong hệ thống và 2 con số M, Z được viết trên đền chủ.

Dòng thứ hai chứa N số nguyên không âm a(1), a(2), …, a(N) (1 <= a(i) <= 10^9+19; 1 <= i <= N), thể hiện tính chất mỗi ngôi đền:

•           Nếu a(i) = 0, ngôi đền thứ i không được đánh số.

•           Nếu a(i) > 0, ngôi đền thứ i được đánh số a(i). Lưu ý là a(1) có thể dương, tức là trên đền chủ ngoài 2 con số M và Z có thể có 1 con số nhằm kích hoạt bẫy sập.

N-1 dòng tiếp theo, mỗi dòng gồm 2 số nguyên X, Y (1 <= X, Y <= N; X != Y), cho biết là có đường nối trực tiếp giữa đền X và đền Y.

Dữ liệu input đảm bảo hệ thống đền có dạng cây.

Output

Một số nguyên duy nhất là số ngôi đền ngách tối đa JM có thể tới và thu thập cổ vật.

Example

Test 1:
Input:
4 1000 6
3 3 0 0
1 2
1 3
1 4
Output:
2

Test 2:
Input:
7 1000 6
3 0 3 3 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7
Output:
1

Giải thích:

Ta sẽ tô đỏ những ngôi đền có đánh số (số tương ứng được viết bằng màu trắng ở trong).
Ở ví dụ 1, có 3 ngôi đền ngách là 2, 3 và 4. JM không thể đi tới ngôi đền 2, vì (3 * 3) % 1000 = 9 > 6.

Giải thích tương tự cho ví dụ 2: có 4 ngôi đền ngách là 4, 5, 6, 7; nhưng vì (3 * 3) % 1000 = 9 > 6 nên JM chỉ có thể đi tới ngôi đền 5.