Balanced Tree

A tree is a structure of $n$ vertices numbered $1$ through $n$ and $n - 1$ edges placed so that exactly one path runs between any two vertices. Each vertex holds exactly one character, either the capital letter A or the capital letter B.

The tree is balanced if no edge joins two vertices that hold the same letter. You can try to balance the tree with a sequence of steps. In one step you choose one edge and swap the characters written in the two vertices that the edge joins.

Determine the minimum number of steps needed to balance the given tree.

The first line contains the number of vertices $n$ ($1 \le n \le 300\,000$).

The second line contains a string of $n$ characters, each of them the capital letter A or the capital letter B. The $j$-th character of the string is the character initially written in vertex $j$.

Each of the next $n - 1$ lines contains two different positive integers $x$ and $y$ ($1 \le x, y \le n$), the labels of two vertices joined directly by an edge. The vertices and edges form a tree as described above.

Print the minimum number of steps. If the tree cannot be balanced, print -1.

The answer can exceed the range of a 32-bit integer.