Chuồng mới của Farmer John có một thiết kế thực sự kỳ lạ: chuồng gồm \(N\) căn phòng (\(2\leq N\leq 2500\)), được đánh số thuận tiện \(1\ldots N\), và \(N-1\) hành lang. Mỗi hành lang nối một cặp phòng sao cho có thể đi từ bất kỳ phòng nào đến bất kỳ phòng nào khác qua một dãy hành lang.

Mỗi phòng trong chuồng có một chiếc đồng hồ tròn trên tường, với các số nguyên tiêu chuẩn \(1\ldots 12\) xung quanh mặt đồng hồ. Tuy nhiên, những chiếc đồng hồ này chỉ có một kim, và kim luôn chỉ thẳng vào một trong các số trên mặt đồng hồ (không bao giờ chỉ vào khoảng giữa hai số).

Bessie muốn đồng bộ tất cả đồng hồ trong chuồng để chúng đều chỉ số \(12\). Tuy nhiên, cô khá đơn giản, và trong lúc đi quanh chuồng, mỗi khi bước vào một phòng, cô lại dịch kim đồng hồ trong phòng đó tiến thêm một vị trí. Chẳng hạn, nếu đồng hồ đang chỉ số \(5\) thì sau đó sẽ chỉ số \(6\); nếu đang chỉ số \(12\) thì sau đó sẽ chỉ số \(1\). Nếu Bessie bước vào cùng một phòng nhiều lần, mỗi lần bước vào cô đều làm đồng hồ trong phòng đó tiến thêm một vị trí.

Hãy xác định số căn phòng mà Bessie có thể bắt đầu hành trình sao cho cô có khả năng đưa tất cả đồng hồ về số \(12\). Lưu ý rằng ban đầu Bessie không làm đồng hồ trong phòng xuất phát tiến lên, nhưng cô sẽ làm nó tiến lên mỗi khi quay lại phòng đó. Các đồng hồ không tự chạy; một đồng hồ chỉ tiến lên khi Bessie bước vào phòng chứa nó. Ngoài ra, một khi Bessie đi vào một hành lang, cô phải đi ra ở đầu bên kia (không được đi một phần hành lang rồi quay ngược về cùng phòng).

Phân nhóm

• Các test 2-7 thỏa mãn \(N\le 100\).
• Các test 8-15 không có ràng buộc bổ sung.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Dòng tiếp theo chứa \(N\) số nguyên, mỗi số thuộc đoạn \(1\ldots 12\), cho biết trạng thái ban đầu của đồng hồ trong từng phòng. Mỗi dòng trong \(N-1\) dòng tiếp theo mô tả một hành lang bằng hai số nguyên \(a\) và \(b\), mỗi số thuộc đoạn \(1\ldots N\), là số hiệu hai phòng được hành lang nối với nhau.

Dữ liệu ra

In số căn phòng mà Bessie có thể xuất phát để có thể đưa tất cả đồng hồ về số \(12\).

Ví dụ

4
11 10 11 11
1 2
2 3
2 4

1

Nguồn

USACO 2020 February Contest, Silver - Clock Tree: https://usaco.org/index.php?page=viewproblem2&cpid=1016

Tác giả: Brian Dean.