던전 디자인

여러분은 마비노기의 새로운 던전을 디자인하는 개발자이다. 현재, 여러분은 던전의 밸런스를 맞추기 위해 고심하고 있다.

던전은 $N$ 개의 방으로 구성되어 있으며, $M$ 개의 복도가 서로 다른 두 방을 양방향으로 연결한다. 각 방에는 $1$부터 $N$까지의 번호가 붙어 있다. 방들은 두 종류로 나뉘는데, 몬스터를 처치해야 하는 방과 보상 상자가 있는 방이다. 던전의 모든 방은 하나 이상의 복도를 통해 서로 연결되어 있으며, 두 방 사이에는 최대 하나의 복도만 존재한다.

이 던전의 특징은 플레이어가 입장하면, 무작위로 선택된 방에서 시작한다는 점이다. 플레이어는 무작위로 선택된 방에서 시작하여 복도를 통해 이동하며, 시작한 방을 포함하여 이미 방문한 방은 다시 방문하지 않는다.

여러분은 플레이어가 두 개 이상의 방을 방문한 어떠한 순간에도, 지금까지 방문한 방 중 보상 상자가 있는 방의 수가 몬스터가 있는 방의 수보다 많아지지 않기를 원한다. 이는 보상이 너무 많으면 플레이어들이 느끼는 재미가 반감될 수 있기 때문이다. 현재 던전은 이 조건을 만족하지 않을 수 있으므로, 새로운 방을 추가하여 이 조건을 만족해야 한다.

여러분은 기존 복도 위에 하나 이상의 방을 추가할 수 있다. 새로 추가된 방은 몬스터가 있는 방이거나 보상 상자가 있는 방이어야 한다. 예를 들어, $1$번 방과 $2$번 방을 연결하는 복도 위에 세 개의 방 $x$, $y$, $z$를 새로 추가하면, $1 \textrm{ --- } x \textrm{ --- } y \textrm{ --- } z \textrm{ --- } 2$와 같은 형태가 된다.

던전의 초기 상태를 나타내는 $N$ 개의 방과 $M$ 개의 복도에 대한 정보가 주어졌을 때, 문제의 조건을 만족하기 위해 추가해야 하는 방의 최소 개수를 출력하는 프로그램을 작성하라.

입력 형식

첫 줄에 방의 수를 나타내는 정수 $N$과 복도의 수를 나타내는 정수 $M$이 공백으로 구분되어 주어진다. ($2 \le N \le 200\,000;$ $N-1 \le M \le 200\,000$)

그다음 줄에 알파벳 대문자 A와 B로 구성된 길이 $N$인 문자열 $S$가 주어진다. $S$의 $i$ 번째 문자는 $i$번 방의 종류를 나타낸다. 문자가 A인 경우 해당 방에는 보상 상자가 있으며 B인 경우 몬스터가 있음을 의미한다.

이어지는 $M$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 복도에 대한 정보를 나타내는 두 정수 $u_i$와 $v_i$가 공백으로 구분되어 주어진다. 이는 $i$ 번째 복도가 $u_i$번 방과 $v_i$번 방을 잇는다는 것을 의미한다. ($1 \le u_i, v_i \le N$; $u_i \neq v_i$)

출력 형식

첫 줄에 문제의 조건을 만족하기 위해 추가해야 하는 방의 최소 개수를 출력한다.

예제 1

3 2
ABA
1 2
2 3

1

예제 2

4 6
BBBA
1 2
1 3
1 4
2 3
2 4
3 4

0

예제 설명

입력 예제 1에서, $1$번 방과 $2$번 방을 연결하는 복도 위에 몬스터가 있는 방을 하나 추가하면 문제의 조건을 만족한다.

입력 예제 2에서는 이미 문제의 조건을 만족하여 방을 추가할 필요가 없다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설