30185번 - 사과 바나나 나무

문제

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

사과 바나나 나무는 정점이 $N$개인 나무(Tree)이며, 두 정점을 잇는 $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을 출력한다.

제한

힌트