ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#10385

모두 바꾸기 60s 1024MB

問題

Banana Rocks Inc는 흔히 쓰이는 편집 연산인 "replace all"(모두 바꾸기)을 수행하는 혁신적인 기술을 개발 중이다. 이 구현은 어떤 텍스트 안에서 특정 문자 하나가 등장하는 모든 위치를 다른 문자로 치환한다. (그 문자가 텍스트에 등장하지 않더라도 연산은 수행되지만 아무 변화도 일어나지 않는다.)

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

불행히도 구현이 미완성이라, 미리 정해진 N개의 문자 쌍 목록에 대해서만 치환을 수행할 수 있다. 또한 어떤 문자 c1을 다른 문자 c2로 바꾸는 치환이 구현되어 있더라도, 그 역방향 치환( c2를 c1로 바꾸기 )은 구현되어 있을 수도 있고 아닐 수도 있다.

당신은 구현된 모든 치환을 전부 시도해 보고 싶다. 초기 문자열 S가 주어진다. 당신은 치환을 여러 번, 순서대로 수행할 수 있다. 첫 번째 치환은 S에 대해 수행되고, (i+1)번째 치환은 i번째 치환을 적용한 결과에 대해 수행된다. 유일한 조건은 구현된 각 치환을 이 과정 중 최소 한 번씩은 반드시 수행해야 한다는 것이다. 각 치환을 몇 번 수행할 수 있는지에는 상한이 없다.

허용되는 문자는 10진수 숫자와 영문 대문자/소문자이다. 이 문제에서는 같은 알파벳이라도 대문자와 소문자를 서로 다른 문자로 취급한다.

마지막 치환을 수행한 결과로 얻은 텍스트에 등장할 수 있는 서로 다른 문자의 최대 개수는 얼마인가?


入力

입력의 첫 줄에는 테스트 케이스 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 2줄로 이루어진다. 첫 줄에는 문자열 S와 정수 N이 주어지며, 이는 각각 초기 텍스트와 구현된 치환의 개수이다. 둘째 줄에는 N개의 길이 2인 문자열 R1, R2, ..., RN이 주어지며, 이는 구현된 치환들을 나타낸다. Ai, Bi는 각각 Ri의 첫 번째/두 번째 문자이다. 즉 i번째로 구현된 치환은 텍스트에서 Ai가 등장하는 모든 곳을 Bi로 바꾸는 연산이다.


出力

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 구현된 모든 치환을 어떤 순서로든(각각 최소 1번 이상) S에 적용했을 때, 마지막으로 얻는 텍스트에 등장할 수 있는 서로 다른 문자의 최대 개수이다.


例題 

4
CODEJAMWORLDFINALS 2
AO OY
xyz 3
xy zx yz
CJ 4
20 2O HC KS
AB 2
Ab bA
Case #1: 14
Case #2: 2
Case #3: 2
Case #4: 2
위의 케이스들은 테스트 세트 1의 제한을 만족한다. 그 제한을 만족하지 않는 다른 샘플 케이스가 이 섹션의 끝에 나온다. 샘플 케이스 #1은 문제 설명에 나온 경우이다. 설명에 나온 순서대로 치환하면 최종 문자열에 서로 다른 문자가 13개가 된다. 하지만 반대 순서로 각각 한 번씩 치환하면 CYDEJOMWYRLDFINOLS를 얻을 수 있고, 서로 다른 문자가 14개가 된다. 샘플 케이스 #2에서는 왼쪽에서 오른쪽 순서대로 한 번씩 치환하는 것이 서로 다른 문자 2개를 만드는 한 가지 방법이다. 샘플 케이스 #3에서는 어떤 치환도 텍스트에 영향을 주지 않으므로 어떻게 적용해도 상관없다. 항상 원래의 두 글자가 그대로 남는다. 치환 문자열에 초기 텍스트에 없는 문자가 포함될 수도 있고, 초기 텍스트에 치환에 등장하지 않는 문자가 있을 수도 있음을 유의하라. 샘플 케이스 #4에서는 대문자 B는 소문자 b와 다른 문자임을 기억하라. 다음 추가 케이스는 테스트 세트 1에는 나오지 않지만 테스트 세트 2에는 나올 수 있다. 1 1234 5 12 2X X3 31 X2 정답 출력은 Case #1: 4이다. 이 추가 샘플에서는 예를 들어 다음 순서로 치환을 수행할 수 있다: X3 2X X2 2X 12 31. 이 과정에서 문자열은 S부터 시작해 다음과 같이 변한다: 1234 1234 1X34 1234 1X34 2X34 2X14.

出典

GCJ 2020wf E

ログインしないとコードを書けません。