La planta de energía Antonio Guiteras tiene ~N~ bases numeradas del ~1~ al ~N~. Las bases están conectadas por ~N-1~ cables. El i-ésimo cable ~(1 \le i \le N-1)~ conecta la base ~A_i~ y la base ~B_i~, en ambas direcciones. Podemos viajar desde cualquier base a cualquier otra base pasando por algunos cables.

Cada base de la planta de energía tiene como máximo un generador de energía. Cada generador de energía tiene un interruptor. Al principio, el interruptor de cada generador de energía está apagado. Eres el director de la planta de energía. Puedes elegir algunos generadores de energía y encender los interruptores de los generadores de energía elegidos. (Está permitido no elegir ninguno). Los generadores de energía tienen las siguientes propiedades:

• Supongamos que las bases ~(x, y, z)~ tienen generadores de energía. Además, supongamos que podemos viajar desde la base ~x~ a la base ~y~ y desde la base ~y~ a la base ~z~, en este orden, de modo que no pasamos por el mismo cable dos veces. Si los interruptores de los generadores de energía de la base ~x~ y la base ~z~ están encendidos, entonces el generador de energía de la base ~y~ está roto.

• Un generador de energía se activará si su interruptor está encendido y no está roto.

Finalmente, obtendrás recompensas de los generadores de energía activados. Obtendrás 1 peso por cada generador de energía activado. Sin embargo, también tendrás que pagar los gastos de reparación de los generadores de energía rotos. Tendrás que pagar 1 peso por cada generador de energía roto. La cantidad total de recompensas menos la cantidad total de gastos de reparación será tu beneficio.

Escribe un programa que, dada la disposición de las bases y los cables, y la información de los generadores de energía, calcule el máximo de tu beneficio.

Entrada

Lee los siguientes datos desde la entrada estándar.
~N~
~A_1, B_1~
~. . . ~
~A_{N-1}, B_{N-1}~
~S~

Aquí ~S~ es una cadena de longitud ~N~ que representa los generadores de energía de las bases. Cada carácter de ~S~ es 0 o 1. El i-ésimo carácter ~(1 \le i \le N)~ describe el generador de energía de la base ~i~. Es 0 si no hay un generador de energía en la base ~i~. Es 1 si la base ~i~ tiene un generador de energía.

Salida

Escribe una línea en la salida estándar. La salida debe contener el máximo de tu beneficio cuando eliges algunos generadores de energía y enciendes todos los interruptores de los generadores de energía elegidos.

Restricciones

• ~1 \le N \le 200 000~.
• ~1 \le A_i \le N (1 \le i \le N-1)~.
• ~1 \le B_i \le N (1 \le i \le N-1)~.
• ~A_i , B_i (1 \le i \le N-1)~.
• Podemos viajar desde cualquier base a cualquier otra base pasando por algunos cables.
• ~S~ es una cadena de longitud ~N~ que consiste en 0, 1.
• ~S~ contiene al menos un 1.

Subtareas

Subtarea 1 ( 6 puntos): ~N \le 16.~
Subtarea 2 (41 puntos): ~N \le 2 000.~
Subtarea 3 (53 puntos): Sin restricciones adicionales.

Ejemplo de Entrada

6
2 3
4 3
1 3
3 5
6 2
110011

Ejemplo de Salida

3

En este ejemplo las bases 1, 2, 5, 6 tienen generadores de energia. Si enciendes las bases 1, 2, 5 se activaran dichos generadores. Es demostrable que no existe una mejor opción, tenga en cuenta que si encendemos la base 6, la base 2 estara rota y por tanto la respuesta sería 2.