32275번 - 보물 찾기 게임

1번부터 $N$번까지의 $N$개의 정점과 $M$개의 양방향 간선으로 연결된 그래프가 있다. 그래프의 각 정점은 최소 하나의 간선과 연결되어 있다. $N$개의 정점 중 몇 개의 정점은 Alice의 소유이고, 다른 정점들은 Bob의 소유이다. 또한, 정점들 중 일부에는 보물이 존재한다.

Alice와 Bob은 그래프의 한 정점에 말을 놓고 게임을 하려고 한다. 각 턴이 시작할 때 말이 Alice의 정점에 있다면 Alice가, Bob의 정점에 있다면 Bob이 현재 정점에 이웃한 간선 하나를 선택해 반대쪽 끝점으로 이동시켜야 한다(원래 위치에 멈춰있을 수 없다). 보물이 있는 정점에 방문하면 보물을 하나 얻으며, 이미 방문한 정점에 다시 방문하더라도 보물이 있는 정점이라면 다시 보물 하나를 얻는다.

Alice의 목표는 게임을 통해 보물이 있는 정점에 무한히 방문하는 것이며, Bob의 목표는 이를 막는 것이다. 엄밀하게 정의하면, $10^{100}$턴 동안 게임을 진행할 때 $10^{90}$번 이상의 턴에서 말이 보물이 있는 정점에 있다면 Alice의 승리, 아니면 Bob의 승리이다.

Alice와 Bob은 항상 최적의 전략으로 플레이할 때, 모든 정점 각각에 대해 각 정점에 말을 놓고 게임을 시작할 때 누가 승리하는지 출력하시오.

파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 $T$ 가 주어지고,

이후 차례로 $T$ 개의 테스트 케이스가 주어진다. ($1 \le T \le 50$)

각 테스트 케이스의 첫 줄에는 정수 $N, M$이 주어진다 ($1 \le N \le 100\,000, 1 \le M \le 200\,000$).

다음 줄에는 길이 $N$의 문자열이 주어진다. 각 문자는 A 또는 B이며, $i$번째 문자가 A이면 $i$번 정점이 Alice의 소유임을, B이면 Bob의 소유임을 뜻한다.

다음 줄에는 길이 $N$의 문자열이 주어진다. 각 문자는 T 또는 .이며, $i$번째 문자가 T이면 $i$번 정점에 보물이 있음을, .이면 보물이 없을을 뜻한다.

다음 $M$개의 줄에는 간선의 정보가 주어진다.

$M$개의 줄 중 $i$번째 줄에는 $i$번째 간선의 양 끝점의 번호 $u_i, v_i$가 공백을 사이에 두고 주어진다 ($1 \le u_i, v_i \le N, u_i \neq v_i$ ). 동일한 정점 쌍을 잇는 간선이 둘 이상 존재하지 않는다.

모든 테스트 케이스에서 $N$의 합 및 $M$의 합은 $2\,000\,000$을 넘지 않는다.

각 테스트 케이스마다 첫 줄에는 “Case #$C$”를 출력하여야 한다. 이때 $C$는 테스트 케이스의 번호이다.

다음 줄에는 길이 $N$의 A 또는 B로 이루어진 문자열을 출력한다. $i$번 정점에 말을 놓고 게임을 시작할 때 Alice가 승리하면 A, Bob이 승리하면 B를 출력해야 한다.