모두 바꾸기

Banana Rocks Inc는 흔히 쓰이는 편집 연산인 "모두 바꾸기"를 수행하는 혁신적인 기술을 개발하고 있다. 이 구현은 주어진 텍스트 안에 나타나는 어떤 문자의 모든 항목을 다른 문자로 바꾼다. (그 문자가 텍스트에 나타나지 않으면 연산은 수행되지만 아무런 효과가 없다.)

예를 들어 시작 텍스트가 CODEJAMWORLDFINALS이고 A을 O로 바꾸는 연산을 수행하면 새 텍스트는 CODEJOMWORLDFINOLS이 된다. 그 결과에 O을 Y로 바꾸는 또 다른 연산을 수행하면 최종 텍스트는 CYDEJYMWYRLDFINYLS이 된다.

안타깝게도 구현이 완성되지 않았으므로, 특정한 N개의 문자 쌍 목록에 있는 치환만 수행할 수 있다. 또한 특정 문자 $c_{1}$을 다른 문자 $c_{2}$로 바꾸는 치환이 구현되어 있더라도, $c_{2}$을 $c_{1}$로 바꾸는 반대 방향의 치환은 구현되어 있을 수도 있고 그렇지 않을 수도 있다.

구현된 모든 치환을 사용해 보려고 한다. 초기 텍스트로 사용할 초기 문자열 S가 주어진다. 치환을 순차적으로 몇 번이든 수행할 수 있다. 첫 번째 치환은 S에 수행하고, (i+1)번째 치환은 i번째 치환을 수행한 결과에 수행한다. 유일한 조건은 이 과정에서 구현된 각 치환을 적어도 한 번 수행해야 한다는 것이다. 각 치환을 수행할 수 있는 횟수에는 상한이 없다.

허용되는 문자는 십진 숫자와 영문 대문자 및 소문자이다. 이 문제에서는 같은 영문자의 대문자와 소문자를 서로 다른 문자로 취급한다.

마지막으로 수행한 치환의 결과인 텍스트에 나타날 수 있는 서로 다른 문자의 최대 개수는 얼마인가?

제한

시간 제한: 테스트 세트당 60초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 모든 i에 대해, 2 ≤ S의 길이 ≤ 1000. S의 각 문자는 영문 대문자, 영문 소문자 또는 십진 숫자이다. 모든 i에 대해, $A_{i}$은 영문 대문자, 영문 소문자 또는 십진 숫자이다. 모든 i에 대해, $B_{i}$은 영문 대문자, 영문 소문자 또는 십진 숫자이다. 모든 i에 대해, $A_{i}$ ≠ $B_{i}$. 모든 i ≠ j에 대해, ($A_{i}$, $B_{i}$) ≠ ($A_{j}$, $B_{j}$). (각 치환은 서로 다르다.)

테스트 세트 1 (공개 판정)

2 ≤ N ≤ 62. 모든 i ≠ j에 대해, $B_{i}$ ≠ $B_{j}$.

테스트 세트 2 (비공개 판정)

2 ≤ N ≤ 62 × 61.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 초기 텍스트를 나타내는 문자열 S와 구현된 치환의 수를 나타내는 정수 N이 주어진다. 둘째 줄에는 구현된 치환을 나타내는 N개의 두 글자 문자열 $R_{1}$, $R_{2}$, ..., $R_{N}$가 주어진다. $A_{i}$과 $B_{i}$은 각각 $R_{i}$의 첫 번째 문자와 두 번째 문자이다. i번째로 구현된 치환은 $A_{i}$의 모든 항목을 $B_{i}$로 바꾸는 것에 해당한다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y은 구현된 모든 치환을 어떤 순서로 각각 한 번 이상 S에 수행한 결과인 텍스트에 나타날 수 있는 서로 다른 문자의 최대 개수이다.

위의 케이스들은 테스트 세트 1의 제한을 만족한다. 이 제한을 만족하지 않는 또 다른 예제 케이스가 이 절의 끝에 나온다.

예제 케이스 #1은 문제 설명에 나온 케이스이다. 문제 설명에서 언급한 순서로 치환을 수행하면 최종 텍스트에 서로 다른 문자가 13개 생긴다는 점에 유의하라. 그러나 두 치환을 각각 한 번씩 반대 순서로 수행하면 서로 다른 문자가 14개인 CYDEJOMWYRLDFINOLS을 얻을 수 있다.

예제 케이스 #2에서 최종 텍스트에 서로 다른 문자 2개를 얻는 한 가지 방법은 주어진 치환들을 왼쪽에서 오른쪽 순서로 각각 한 번씩 수행하는 것이다.

예제 케이스 #3에서는 어떤 치환도 텍스트에 전혀 영향을 주지 않으므로 치환을 어떤 방식으로 적용하는지는 중요하지 않다. 항상 원래의 두 글자가 남는다. 치환에는 초기 텍스트에 나타나지 않는 문자가 포함될 수 있고, 초기 텍스트에는 구현된 치환에 나타나지 않는 문자가 포함될 수 있다는 점에 유의하라.

예제 케이스 #4에서는 대문자 B이 소문자 b과 같은 문자가 아니라는 점을 기억하라.

다음 추가 케이스는 테스트 세트 1에는 나올 수 없지만 테스트 세트 2에는 나올 수 있다.

올바른 출력은 Case #1: 4이다.

이 추가 예제 케이스에서 가능한 한 가지 방법은 X3 2X X2 2X 12 31 순서로 치환을 수행하는 것이다. 이 과정에서 S로 시작하여 다음 문자열들을 거친다: 1234 1234 1X34 1234 1X34 2X34 2X14.