균형 잡힌 트리

트리는 $1$번부터 $n$번까지 번호가 붙은 정점 $n$개와 간선 $n - 1$개로 이루어진 구조이며, 두 정점 사이에는 언제나 경로가 하나만 존재한다. 각 정점에는 대문자 A 또는 대문자 B가 정확히 하나씩 적혀 있다.

같은 글자가 적힌 두 정점을 잇는 간선이 하나도 없으면 그 트리는 균형 잡힌 트리다. 여러 단계를 거쳐 트리를 균형 잡힌 상태로 만들 수 있다. 한 단계에서는 간선 하나를 고르고, 그 간선이 잇는 두 정점에 적힌 글자를 서로 바꾼다.

주어진 트리를 균형 잡힌 상태로 만드는 데 필요한 최소 단계 수를 구하시오.

첫째 줄에 트리의 정점 개수 $n$ ($1 \le n \le 300\,000$)이 주어진다.

둘째 줄에 길이가 $n$인 문자열이 주어진다. 각 문자는 대문자 A 또는 대문자 B이고, 이 문자열의 $j$번째 문자가 정점 $j$에 처음 적혀 있는 글자다.

다음 $n - 1$개 줄에는 각각 서로 다른 두 자연수 $x$와 $y$ ($1 \le x, y \le n$)가 주어진다. 정점 $x$와 정점 $y$가 간선 하나로 직접 연결되어 있다는 뜻이다. 주어지는 정점과 간선은 문제에서 설명한 트리를 이룬다.

필요한 최소 단계 수를 출력한다. 트리를 균형 잡힌 상태로 만들 수 없으면 -1을 출력한다.

답은 32비트 정수 범위를 벗어날 수 있다.