Đề bài

Công ty Banana Rocks Inc đang phát triển một công nghệ mang tính cách mạng để thực hiện thao tác chỉnh sửa phổ biến "thay thế tất cả". Cách cài đặt của họ thay mọi lần xuất hiện của một ký tự trong một văn bản cho trước bằng một ký tự khác. (Nếu ký tự đó không xuất hiện trong văn bản thì thao tác vẫn được thực hiện, nhưng không gây ra thay đổi nào.)

Ví dụ, nếu văn bản ban đầu là CODEJAMWORLDFINALS và ta thay A bằng O, văn bản mới là CODEJOMWORLDFINOLS. Nếu tiếp tục thay O bằng Y, văn bản cuối cùng là CYDEJYMWYRLDFINYLS.

Đáng tiếc là phần cài đặt chưa hoàn chỉnh, nên nó chỉ thực hiện được các phép thay thuộc một danh sách cụ thể gồm N cặp ký tự. Ngay cả khi phép thay \(c_1\) bằng \(c_2\) đã được cài đặt, phép thay ngược từ \(c_2\) thành \(c_1\) có thể có hoặc không.

Bạn muốn thử tất cả các phép thay đã được cài đặt. Bạn được cho chuỗi S làm văn bản ban đầu và có thể thực hiện số lượng tùy ý các phép thay theo thứ tự liên tiếp: phép thứ nhất áp dụng lên S, phép thứ \((i+1)\) áp dụng lên kết quả của phép thứ \(i\). Yêu cầu duy nhất là mỗi phép thay đã cài đặt phải được thực hiện ít nhất một lần. Không có giới hạn trên cho số lần thực hiện mỗi phép.

Các ký tự được phép là chữ số thập phân, chữ cái tiếng Anh viết hoa và viết thường. Dạng viết hoa và viết thường của cùng một chữ cái được xem là hai ký tự khác nhau.

Hỏi số ký tự phân biệt lớn nhất có thể xuất hiện trong văn bản sau phép thay cuối cùng là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số bộ dữ liệu T. Mỗi bộ dữ liệu gồm hai dòng. Dòng đầu chứa chuỗi S và số nguyên N: văn bản ban đầu và số phép thay đã cài đặt.

Dòng thứ hai chứa N chuỗi hai ký tự \(R_1,R_2,\ldots,R_N\). Gọi \(A_i,B_i\) lần lượt là ký tự thứ nhất và thứ hai của \(R_i\). Phép thứ \(i\) thay mọi lần xuất hiện của \(A_i\) bằng \(B_i\).

Dữ liệu ra

Với mỗi bộ dữ liệu, in một dòng dạng Case #x: y, trong đó x là số thứ tự bộ dữ liệu (bắt đầu từ 1), và y là số ký tự phân biệt lớn nhất có thể có sau khi áp dụng lên S tất cả các phép thay đã cài đặt, mỗi phép ít nhất một lần, theo một thứ tự nào đó.

Ràng buộc

• \(1 \le T \le 100\).
• \(2 \le |S| \le 1000\).
• Mỗi ký tự của S, mỗi \(A_i\) và mỗi \(B_i\) là chữ cái tiếng Anh viết hoa, viết thường hoặc chữ số thập phân.
• \(A_i \ne B_i\) với mọi \(i\).
• \((A_i,B_i) \ne (A_j,B_j)\) với mọi \(i \ne j\); mỗi phép thay là duy nhất.

Phân nhóm

Test Set 1 (phán quyết hiển thị)

• \(2 \le N \le 62\).
• \(B_i \ne B_j\) với mọi \(i \ne j\).

Test Set 2 (phán quyết ẩn)

• \(2 \le N \le 62 \times 61\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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
1234 5
12 2X X3 31 X2

Nguồn

Google Code Jam 2020, Chung kết thế giới trực tuyến, bài Replace All.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.