Furthest Different Colored Nodes

You are given a tree with n nodes. Each node is colored either black or white.

Your task is to find the maximum distance between any pair of nodes that have different colors. The distance between two nodes is defined as the number of edges in the unique path connecting them.

Note: It is guaranteed that the input forms a tree. The nodes are numbered from 1 to n.

Formally, if the colors of nodes i and j are different, and d(i, j) is the number of edges on the path from i to j, you need to determine the maximum value of d(i, j).

inputFormat

The input is given in the following format:

n
s
u1 v1
u2 v2
...
un-1 vn-1

Where:

• n is the number of nodes in the tree.
• s is a string of length n consisting of the characters 'B' and 'W', representing the colors of the nodes (Black or White) in order from node 1 to node n.
• Each of the next n - 1 lines contains two integers ui and vi, denoting an undirected edge between nodes ui and vi.

outputFormat

Output a single integer: the maximum distance between any two nodes that have different colors. If no such pair exists, output 0.

sample

3
WBW
1 2
2 3

1