Mirko je odabrao božićno drvce za nadolazeće blagdane te ga je odlučio ukrasiti božićnim lampicama. Božićne lampice sastoje se od N LED žaruljica povezanih s (N − 1) vodljivih žica tako da su sve žaruljice međusobno povezane. Dodatno, za svaku žaruljicu poznata je boja kojom svijetli.

Nakon što je okitio drvce, Mirko se ponosno zagledao u svoje remek-djelo. Nakon kraćeg gledanja, počeo je uočavati razne uzorke, među kojima su ga se posebno dojmili tzv. palindromski segmenti.

Palindromski segment je dio na božićnim lampicama između dvije žaruljice, u i v, takav da je slijed boja na putu od žaruljice u do žaruljice v jednak slijedu boja na putu od žaruljice v do žaruljice u. Odredite duljinu najdužeg takvog segmenta, izraženu u broju žaruljica na tom segmentu.

Ulazni podaci

U prvom je retku prirodan broj N (1 ≤ N ≤ 50 000) iz teksta zadatka.

U sljedećem se retku nalazi niz od N malih slova engleske abecede gdje i-to slovo predstavlja boju kojom svijetli i-ta žaruljica.

U sljedećih se (N − 1) redaka nalaze po dva broja A i B (1 ≤ A, B ≤ N, A != B), koja označavaju vodljivu žicu koja izravno povezuje žaruljice A i B.

Izlazni podaci

U prvom i jedinom retku ispišite duljinu najdužeg palindromskog segmenta.

Probni primjeri

Ulaz

7
imanade
1 2
2 3
3 4
4 5
5 6
6 7

Izlaz

3

Ulaz

4
aabb
1 2
1 3
3 4

Izlaz

2

Ulaz

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

Izlaz

5