El nuevo granero del granjero John tiene un diseño realmente peculiar: consta de ~N~ habitaciones, convenientemente numeradas del ~1~ al ~N~, y ~N-1~ pasillos. Cada pasillo conecta un par de habitaciones, de forma que es posible ir de cualquier habitación a cualquier otra a lo largo de una serie de pasillos.

Cada habitación del granero tiene un reloj circular en la pared con los números enteros estándar del 1 al 12 alrededor de su esfera. Sin embargo, estos relojes solo tienen una manecilla, que siempre apunta directamente a uno de los números enteros (nunca apunta entre dos de ellos).

Bessie, la vaca, quiere sincronizar todos los relojes del granero para que apunten al 12. Sin embargo, es algo ingenua y, al recorrer el granero, cada vez que entra en una habitación, adelanta la manecilla del reloj una posición. Por ejemplo, si el reloj marcaba las 5, ahora marcaría las 6, y si marcaba las 12, ahora marcaría la 1. Si Bessie entra varias veces en la misma habitación, el reloj de esa habitación avanza cada vez que entra.

Determine el número de habitaciones en las que Bessie podría empezar a caminar alrededor del granero de forma que pudiera, hipotéticamente, poner todos los relojes en 12. Tenga en cuenta que Bessie no avanza inicialmente el reloj de su habitación de inicio, pero lo haría cada vez que volviera a entrar en ella. Los relojes no avanzan solos; un reloj solo avanza si Bessie entra en su habitación. Además, una vez que Bessie entra en un pasillo, debe salir por el otro extremo (no se le permite caminar parcialmente por el pasillo y volver a la misma habitación).

Entrada

• La primera línea de entrada contiene ~N~ ~(2 \leq N \leq 2500)~.
• La siguiente línea contiene ~N~ números enteros, cada uno en el rango ~1...12~, que especifican la hora inicial en cada habitación.
• Las siguientes ~N-1~ líneas describen un pasillo mediante dos números enteros, ~a~ y ~b~, cada uno en el rango ~1...N~, que indican los números de las habitaciones conectadas por el pasillo.

Salida

Imprime el número de habitaciones en las que Bessie podría comenzar, de manera que pueda poner todos los relojes en 12.

Ejemplo de Entrada

4
11 10 11 11
1 2
2 3
2 4

Ejemplo de Salida

1

En este ejemplo, Bessie puede poner todos los relojes en 12 si y solo si comienza en la habitación 2 (por ejemplo, moviéndose a las habitaciones ~1, 2, 3, 2~ y finalmente ~4~).

USACO 2020 February Contest, Silver. Problem 3. Clock Tree.