A central elétrica JOI tem $N$ bases numeradas de $1$ a $N$. As bases estão ligadas por $N-1$ fios. O fio número $i$ ($1 \le i \le N-1$) liga as bases $A_i$ e $B_i$ nos dois sentidos. É possível ir de qualquer base a qualquer outra percorrendo alguns fios.

Cada base da central elétrica JOI tem, no máximo, um gerador. Cada gerador tem um interruptor. Inicialmente, todos os interruptores estão desligados. Como diretor da central, pode escolher alguns geradores e ligar os seus interruptores. (Também pode não escolher nenhum.) Os geradores têm as seguintes propriedades.

• Suponha que as bases $x,y,z$ têm geradores e que é possível ir da base $x$ à base $y$ e depois da base $y$ à base $z$, nesta ordem, sem percorrer o mesmo fio duas vezes. Se os interruptores dos geradores das bases $x$ e $z$ estiverem ligados, o gerador da base $y$ avaria.
• Um gerador é ativado se o seu interruptor estiver ligado e ele não estiver avariado.

Por fim, receberá recompensas pelos geradores ativados: 1 iene por cada um. No entanto, terá de pagar despesas de reparação pelos geradores avariados: 1 iene por cada um. O seu lucro é o total das recompensas menos o total das despesas de reparação.

Escreva um programa que, dada a disposição das bases e dos fios e as informações sobre os geradores, calcule o seu lucro máximo.

Entrada

Leia os seguintes dados da entrada padrão.

$$ \begin{array}{ll} N \\ A_1 & B_1 \\ \vdots \\ A_{N-1} & B_{N-1} \\ S \end{array} $$

Aqui, $S$ é uma cadeia de comprimento $N$ que representa os geradores das bases. Cada caráter de $S$ é 0 ou 1. O caráter número $i$ ($1 \le i \le N$) descreve o gerador da base $i$: é 0 se essa base não tiver gerador e 1 se tiver.

Saída

Escreva uma linha na saída padrão com o lucro máximo que pode obter escolhendo alguns geradores e ligando todos os interruptores dos geradores escolhidos.

Restrições

• $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 \ne B_i$ ($1 \le i \le N-1$).
• É possível ir de qualquer base a qualquer outra percorrendo alguns fios.
• $S$ é uma cadeia de comprimento $N$ composta por 0 e 1.
• $S$ contém pelo menos um 1.

Subtarefas

1. (6 pontos) $N \le 16$.
2. (41 pontos) $N \le 2\,000$.
3. (53 pontos) Sem restrições adicionais.

Exemplos

Entrada 1

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

Saída 1

3

Nota

Neste exemplo, as bases $1,2,5,6$ têm geradores.

Se ligar os interruptores das bases $1,2,5$, os geradores dessas bases serão ativados e receberá 3 ienes. Como não pagará despesas de reparação, o lucro será de 3 ienes. Como este é o lucro máximo, escreva 3.

Por outro lado, se ligar os interruptores das bases $1,5,6$, o gerador da base $2$ avariará e os geradores das bases $1,5,6$ serão ativados. Receberá 3 ienes e pagará 1 iene de despesas de reparação. Portanto, o lucro será de 2 ienes.

Se ligar os interruptores das bases $1,2,5,6$, o gerador da base $2$ avariará e os geradores das bases $1,5,6$ serão ativados. Receberá 3 ienes e pagará 1 iene de despesas de reparação. Portanto, o lucro será de 2 ienes.

Entrada 2

8
1 2
3 5
6 4
4 5
5 2
7 2
2 8
11111111

Saída 2

3

Entrada 3

16
7 10
5 11
9 4
14 12
2 11
14 16
4 2
1 13
11 3
7 1
15 9
2 1
11 6
14 9
8 9
0111111001001110

Saída 3

5