15202번 - Stablo 다국어

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.

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.

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.