Longest Palindromic Path in a Tree

Mirko decorates his Christmas tree using \(N\) LED lights. Each LED light has a known color, and they are connected by \(N-1\) wires forming a tree structure. A palindromic segment is defined as a simple path from node \(u\) to node \(v\) such that the sequence of colors from \(u\) to \(v\) is the same as the sequence from \(v\) to \(u\) (i.e. it forms a palindrome).

Your task is to determine the length (i.e. the number of nodes) of the longest palindromic segment in the tree.

Input Format

The first line contains an integer \(N\) representing the number of LED lights (nodes).
The second line contains a string of length \(N\) where the \(i\)-th character represents the color of the \(i\)-th LED light.
Each of the next \(N-1\) lines contains two integers \(u\) and \(v\) (1-indexed), denoting an undirected edge (wire) connecting nodes \(u\) and \(v\).

Output Format

Output a single integer, which is the maximum number of nodes in a palindromic segment of the tree.

Note: A single node is always a palindromic segment of length 1.

inputFormat

Input begins with an integer \(N\). The next line is a string of length \(N\) representing the colors. Following that, there are \(N-1\) lines, each containing two integers \(u\) and \(v\), indicating an undirected edge between nodes \(u\) and \(v\).

outputFormat

Output a single integer denoting the length of the longest palindromic segment in the tree.

sample

5
abccb
1 2
1 3
2 4
2 5

2