Mỗi năm, giáo sư của bạn dán một tờ đăng ký trống lên cửa phòng để sinh viên đăng ký tham dự một hội nghị nghiên cứu khoa học danh giá. Nếu muốn thuyết trình tại hội nghị, sinh viên chọn một chủ đề gồm hai từ chưa có trên tờ giấy rồi viết chủ đề đó vào. Khi hết hạn đăng ký, giáo sư nhờ một nghiên cứu sinh sắp xếp ngẫu nhiên các chủ đề để không thiên vị người đăng ký sớm hay muộn, rồi đưa danh sách cho bạn xem xét.

Đồ ăn nhẹ ở hội nghị rất ngon, nên một số sinh viên tìm cách giả mạo để được tham dự. Họ lấy từ thứ nhất của một chủ đề đã có trên tờ giấy và từ thứ hai của một chủ đề đã có trên tờ giấy, rồi ghép chúng theo đúng thứ tự đó thành một “chủ đề” mới, miễn là chủ đề mới chưa có trên tờ giấy. Vì giáo sư của bạn rất cởi mở, đôi khi mánh này thật sự thành công!

Những người giả mạo hoàn toàn thiếu sáng tạo và không thể tự nghĩ ra từ thứ nhất hay từ thứ hai mới; họ buộc phải dùng những từ đã có trên tờ giấy. Hơn nữa, họ không dùng một từ vốn xuất hiện ở vị trí thứ nhất làm từ thứ hai của mình, trừ khi từ đó cũng đã xuất hiện ở vị trí thứ hai trên tờ giấy; chiều ngược lại cũng tương tự.

Bạn có danh sách gồm toàn bộ \(N\) chủ đề đã nộp theo một thứ tự tùy ý, nhưng không biết thứ tự thực tế chúng được ghi lên tờ giấy. Số chủ đề lớn nhất có thể đã bị giả mạo là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên \(N\), sau đó là \(N\) dòng. Mỗi dòng biểu diễn một chủ đề khác nhau và chứa hai chuỗi chữ cái tiếng Anh viết hoa: hai từ của chủ đề, theo đúng thứ tự.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là số nguyên lớn nhất các chủ đề có thể đã bị giả mạo.

Ràng buộc

• \(1 \le T \le 100\).
• Độ dài mỗi từ nằm trong đoạn từ 1 đến 20.
• Không có chủ đề nào lặp lại trong cùng một bộ test.

Phân nhóm

• Test Set 1 (Hiển thị): \(1 \le N \le 16\).
• Test Set 2 (Ẩn): \(1 \le N \le 1000\).

Đ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ụ

3
3
HYDROCARBON COMBUSTION
QUAIL BEHAVIOR
QUAIL COMBUSTION
3
CODE JAM
SPACE JAM
PEARL JAM
2
INTERGALACTIC PLANETARY
PLANETARY INTERGALACTIC

Case #1: 1
Case #2: 0
Case #3: 0

Nguồn

Google Code Jam 2016, Vòng 1B, bài Technobabble.

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