사과 바나나 나무

카루나는 과수원을 하나 운영한다. 얼마 전 카루나는 과수원에 "사과 바나나 나무"라는 신기한 나무를 한 그루 심었다.

사과 바나나 나무는 정점이 $N$개인 나무이다. 두 정점을 잇는 가지가 $N-1$개 있어 전체가 하나의 연결 그래프를 이룬다. 각 정점에는 $1$부터 $N$까지의 번호가 매겨져 있고, 각 정점에는 사과 또는 바나나가 하나씩 달려 있다.

사과와 바나나는 관리 방법이 달라서, 카루나는 과일 종류별로 한 덩어리로 모으려 한다. 구체적으로, 나무에서 사과가 달린 정점만 남겼을 때 그 정점들이 하나의 연결 그래프를 이루어야 하고, 바나나가 달린 정점만 남겼을 때도 마찬가지로 하나의 연결 그래프를 이루어야 한다. (정점이 하나도 남지 않는 경우도 하나의 연결 그래프로 본다.)

카루나는 가지로 직접 연결된 두 정점에 달린 과일을 서로 바꿔 달 수 있다. 이를 "이동"이라고 부른다. 이동은 체력을 꽤 소모하므로, 카루나는 가능한 한 적은 횟수의 이동으로 목표를 이루고 싶어 한다.

과일 종류별로 한 덩어리로 모을 수 있는지 판별하고, 가능하다면 필요한 최소 이동 횟수를 구하라.

첫째 줄에 나무의 정점 개수 $N$이 주어진다. ($1\le N\le 200\,000$)

둘째 줄에는 A와 B로만 이루어진 길이 $N$의 문자열이 주어진다. 문자열의 $i$번째 문자는 $i$번 정점에 달린 과일을 나타낸다. A는 사과, B는 바나나이다.

셋째 줄부터 $N-1$개의 줄에 걸쳐 각 가지가 잇는 두 정점의 번호 $u$, $v$가 주어진다. ($1\le u,v\le N$, $u\neq v$)

과일 종류별로 한 덩어리로 모을 수 있다면 필요한 최소 이동 횟수를 출력한다. 모을 수 없다면 -1을 출력한다.