## COCI '19 Contest 3 #4 Lampice

View as PDF

Points: 25 (partial)
Time limit: 5.0s
Memory limit: 512M

Problem types

Mirko chose a Christmas tree for the upcoming holidays and decided to decorate it with Christmas lights. Christmas lights contain LED lights that are connected via conductive wires such that all of the lights are connected. Additionally, we know the color of each Christmas light.

After he decorated the tree, Mirko proudly stared at his masterpiece. After a while, he started noticing different patterns. Among those patterns, he was particularly amazed by so-called palindromic segments. Palindromic segment is a segment of Christmas lights on the path between two fixed lights, and , such that the array of colors on a path from to is exactly the same as the array of colors on the path from to . Determine the length of the longest palindromic segment expressed in the number of lights on that segment.

#### Input

The first line contains an integer from the task description.

The next line contains an array of lowercase letters from the English alphabet where the -th letter represents the color of the -th Christmas light.

Each of the next lines contains two integers and , which denote that lights and are directly connected by a conducting wire.

#### Output

The first line of output should contain the length of the longest palindromic segment.

#### Scoring

Light is directly connected with light .
At most lights are directly connected with exactly one other light.

#### Sample Input 1

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

#### Sample Output 1

3

#### Sample Input 2

4
aabb
1 2
1 3
3 4

#### Sample Output 2

2

#### Sample Input 3

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

#### Sample Output 3

5