Дерево з годинником

Новий амбар Фермера Джона складається з $n$ кімнат, пронумерованих від $1$ до $n$, і $n-1$ коридорів. Кожен коридор з'єднує пару кімнат так, що можна дістатися з будь-якої кімнати до будь-якої іншої через серію коридорів.

У кожній кімнаті амбару є круглий годинник на стіні зі стандартним розташуванням цифр від $1$ до $12$. Проте на цих годинниках є лише одна стрілка, яка завжди вказує точно на одне з цих чисел (вона ніколи не зупиняється між двома числами).

Корова Бессі хоче синхронізувати всі годинники в амбарі, щоб вони показували число $12$. Але через своє коров'яче мислення, кожного разу, коли вона заходить у кімнату, вона переміщує стрілку вперед на одну позицію. Наприклад, якщо стрілка показувала на $5$, Бессі переводить її на $6$. Якщо годинник вказував на $12$, вона переводить стрілку на $1$. Якщо Бессі заходить у кімнату кілька разів, вона переміщує стрілку при кожному вході.

Визначте номери кімнат, з яких Бессі може почати свою подорож по амбару так, щоб усі стрілки годинників стали на $12$. Зазначимо, що Бессі не переміщує стрілку в стартовій кімнаті на початку шляху, але переміщує її при кожному наступному вході. Стрілки самі по собі не рухаються. Бессі, входячи в коридор, повинна дійти до кінця і увійти в кімнату в кінці коридору. Вона не може повернутися назад всередині коридору, щоб знову увійти в кімнату, з якої вийшла.

Вхідні дані

Перший рядок містить число $n(2\le n\le 2500)$. Наступний рядок містить $n$ цілих чисел, кожне в інтервалі $[1,12]$, що вказують початкові положення стрілок у кожній кімнаті. Кожен з наступних $n-1$ рядків описує коридор двома цілими числами $a$ і $b$, кожне в інтервалі $[1,n]$, які задають номери кімнат, з'єднаних цим коридором.

Вихідні дані

Виведіть кількість кімнат, з яких Бессі може почати свій шлях, щоб встановити всі годинники на $12$.

Приклади

У цьому прикладі Бессі може встановити всі годинники на $12$, тільки якщо вона почне свій шлях у кімнаті $2$ (і далі, наприклад, перейшовши в кімнату $1,2,3,2$ і, нарешті, $4$).