Das JOI-Kraftwerk hat $N$ Standorte mit den Nummern $1$ bis $N$. Die Standorte sind durch $N-1$ Leitungen verbunden. Die $i$-te Leitung ($1 \le i \le N-1$) verbindet die Standorte $A_i$ und $B_i$ in beide Richtungen. Von jedem Standort kann man über einige Leitungen jeden anderen Standort erreichen.

An jedem Standort des JOI-Kraftwerks befindet sich höchstens ein Generator. Jeder Generator hat einen Schalter. Anfangs sind die Schalter aller Generatoren ausgeschaltet. Du bist der Leiter des JOI-Kraftwerks. Du darfst einige Generatoren auswählen und ihre Schalter einschalten. (Es ist auch erlaubt, keinen auszuwählen.) Die Generatoren haben die folgenden Eigenschaften.

• Angenommen, an den Standorten $x,y,z$ befinden sich Generatoren. Außerdem sei es möglich, zuerst von Standort $x$ zu Standort $y$ und dann von Standort $y$ zu Standort $z$ zu gelangen, ohne eine Leitung zweimal zu benutzen. Sind die Schalter der Generatoren an den Standorten $x$ und $z$ eingeschaltet, geht der Generator an Standort $y$ kaputt.
• Ein Generator wird aktiviert, wenn sein Schalter eingeschaltet und er nicht kaputt ist.

Am Ende erhältst du eine Vergütung für aktivierte Generatoren. Für jeden aktivierten Generator erhältst du 1 Yen. Allerdings musst du auch Reparaturkosten für kaputte Generatoren bezahlen. Für jeden kaputten Generator musst du 1 Yen bezahlen. Die Gesamtvergütung abzüglich der gesamten Reparaturkosten ist dein Gewinn.

Schreibe ein Programm, das anhand der Anordnung der Standorte und Leitungen sowie der Informationen über die Generatoren deinen maximalen Gewinn berechnet.

Eingabe

Lies die folgenden Daten von der Standardeingabe.

$$ \begin{gathered} N\\ A_1\ B_1\\ \vdots\\ A_{N-1}\ B_{N-1}\\ S \end{gathered} $$

Dabei ist $S$ eine Zeichenkette der Länge $N$, die die Generatoren an den Standorten beschreibt. Jedes Zeichen von $S$ ist entweder 0 oder 1. Das $i$-te Zeichen ($1 \le i \le N$) beschreibt den Generator an Standort $i$. Es ist 0, wenn sich an Standort $i$ kein Generator befindet. Es ist 1, wenn Standort $i$ einen Generator hat.

Ausgabe

Gib eine Zeile auf der Standardausgabe aus. Sie soll deinen maximalen Gewinn enthalten, wenn du einige Generatoren auswählst und die Schalter aller ausgewählten Generatoren einschaltest.

Beschränkungen

• $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$).
• Von jedem Standort kann man über einige Leitungen jeden anderen Standort erreichen.
• $S$ ist eine Zeichenkette der Länge $N$, die aus 0 und 1 besteht.
• $S$ enthält mindestens eine 1.

Teilaufgaben

1. (6 Punkte) $N \le 16$.
2. (41 Punkte) $N \le 2\,000$.
3. (53 Punkte) Keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

3

Hinweis

In diesem Beispiel befinden sich an den Standorten $1,2,5,6$ Generatoren.

Wenn du die Schalter an den Standorten $1,2,5$ einschaltest, werden die Generatoren an diesen Standorten aktiviert und du erhältst 3 Yen. Da keine Reparaturkosten anfallen, beträgt dein Gewinn 3 Yen. Da dies dein maximaler Gewinn ist, gib 3 aus.

Wenn du hingegen die Schalter an den Standorten $1,5,6$ einschaltest, geht der Generator an Standort $2$ kaputt, und die Generatoren an den Standorten $1,5,6$ werden aktiviert. Du erhältst 3 Yen und bezahlst 1 Yen Reparaturkosten. Dein Gewinn beträgt daher 2 Yen.

Wenn du die Schalter an den Standorten $1,2,5,6$ einschaltest, geht der Generator an Standort $2$ kaputt, und die Generatoren an den Standorten $1,5,6$ werden aktiviert. Du erhältst 3 Yen und bezahlst 1 Yen Reparaturkosten. Dein Gewinn beträgt daher 2 Yen.

Eingabe 2

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

Ausgabe 2

3

Eingabe 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

Ausgabe 3

5