Apple Banana Tree

Karuna runs an orchard. Recently Karuna planted a strange tree called the "Apple Banana Tree" in the orchard.

The Apple Banana Tree is a tree with $N$ vertices. There are $N-1$ branches, each connecting two vertices, so the whole thing forms one connected graph. Vertices are numbered from 1 to $N$, and each vertex has either one apple or one banana.

Apples and bananas need different kinds of care, so Karuna wants to gather each kind of fruit into one block. Specifically, when only the vertices with apples are kept, they must form one connected graph. The same must hold for the vertices with bananas. (A case where no vertices remain also counts as one connected graph.)

Karuna can swap the fruits on two vertices joined directly by a branch. This is called a "move." A move takes a lot of stamina, so Karuna wants to reach the goal with as few moves as possible.

Determine whether each kind of fruit can be gathered into one block. If it can, find the minimum number of moves needed.

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

The second line contains a string of length $N$ made only of A and B. The $i$-th character represents the fruit on vertex $i$. A is an apple, and B is a banana.

Each of the following $N-1$ lines contains two vertex numbers $u$ and $v$, the endpoints of a branch. ($1\le u,v\le N$, $u\neq v$)

If each kind of fruit can be gathered into one block, print the minimum number of moves needed. Otherwise, print -1.