Stablo je struktura koja se sastoji od n vrhova označenih brojevima od 1 do n i n − 1 bridova postavljenih tako da izmedu svaka dva vrha stabla postoji jedinstven put. Dodatno, u svaki vrh je upisan točno jedan znak i to veliko slovo Aili veliko slovo B.</p>

Stablo je uravnoteženo ako ne postoji brid koji povezuje vrhove označene istim slovom. Stablo možemo pokušati uravnotežiti nizom koraka gdje u svakom koraku odaberemo jedan brid i zamijenimo znakove zapisane u vrhovima koje brid povezuje.

Odredite minimalan broj koraka potrebnih da se uravnoteži zadano stablo.

입력 형식

U prvom redu nalazi se prirodni broj n (1 ≤ n ≤ 300 000) — broj vrhova stabla. Sljedeći red sadrži niz od n znakova gdje je svaki znak veliko slovo Aili B— j-ti znak u nizu je znak inicijalno zapisan u vrhu j.</p>

Svaki od sljedećih n − 1 redova sadrži dva različita prirodna broja x i y (1 ≤ x, y ≤ n) — oznake vrhova direktno povezanih bridom. Vrhovi i bridovi čine stablo kao što je opisano u tekstu zadatka.

출력 형식

Ispišite traženi minimalni broj koraka. Ako nije moguće uravnotežiti stablo, ispišite -1.

예제 입력 1

6
AABBAB
1 2
1 3
3 4
3 5
1 6

예제 출력 1

2

예제 입력 2

4
AABB
1 2
1 3
1 4

예제 출력 2

-1

예제 입력 3

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

예제 출력 3

5