보물 찾기 게임

1번부터 $N$번까지 $N$개의 정점과 $M$개의 양방향 간선으로 이루어진 그래프가 있다. 모든 정점은 적어도 하나의 간선과 연결되어 있다. 정점 중 일부는 Alice의 소유이고, 나머지는 Bob의 소유이다. 정점 일부에는 보물이 있다.

Alice와 Bob은 그래프의 한 정점에 말을 놓고 게임을 한다. 턴이 시작할 때 말이 Alice의 정점에 있으면 Alice가, Bob의 정점에 있으면 Bob이 현재 정점과 이웃한 간선 하나를 골라 반대쪽 끝점으로 말을 옮겨야 한다. 말을 제자리에 둘 수는 없다.

말이 보물이 있는 정점에 도착하면 보물을 하나 얻는다. 이미 방문한 정점이라도 보물이 있는 정점이라면 말이 다시 올 때마다 보물을 하나씩 더 얻는다.

Alice의 목표는 말이 보물이 있는 정점을 무한히 방문하도록 하는 것이고, Bob의 목표는 이를 막는 것이다. 정확히 말하면, $10^{100}$턴 동안 게임을 진행했을 때 $10^{90}$번 이상의 턴에서 말이 보물이 있는 정점에 있으면 Alice가 이기고, 그렇지 않으면 Bob이 이긴다.

두 사람이 항상 최적의 전략으로 플레이할 때, 각 정점에서 게임을 시작하면 누가 이기는지 구하시오.

첫 줄에 테스트 케이스의 개수 $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$개의 줄에는 간선의 양 끝점 번호 $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$는 테스트 케이스 번호이다. 다음 줄에는 A 또는 B로 이루어진 길이 $N$의 문자열을 출력한다. $i$번 정점에 말을 놓고 게임을 시작할 때 Alice가 이기면 A, Bob이 이기면 B를 출력한다.