Bạn có \(2n\) viên bi trên một lưới ô vuông. Các viên bi được tô bằng \(n\) màu khác nhau sao cho có đúng 2 viên bi mỗi màu. Các viên bi được đặt tại các tọa độ \((1,0), (2,0), \dots, (2n, 0)\).

Nhiệm vụ của bạn là vẽ một đường đi cho mỗi màu để nối hai viên bi cùng màu đó. Mỗi đường đi phải bao gồm các đoạn thẳng nằm ngang hoặc thẳng đứng giữa các điểm lưới. Không có hai đường đi nào được giao nhau hoặc chạm nhau. Không có đường đi nào được cắt đường thẳng \(y=0\). Mỗi đường đi chỉ có thể chạm đường thẳng \(y=0\) tại vị trí của hai viên bi mà nó đang nối, vì vậy đoạn thẳng đầu tiên và cuối cùng của mỗi đường đi phải là đoạn thẳng đứng.

Cho một cách sắp xếp các viên bi, hãy trả về chiều cao tối thiểu của một giải pháp, hoặc trả về -1 nếu không tồn tại giải pháp. Chiều cao được định nghĩa là hiệu giữa tọa độ \(Y\) cao nhất và thấp nhất của các đường đi được sử dụng.

Một ví dụ:

red red blue yellow blue yellow

Một giải pháp có thể là:

 +---+    +-----------+
 |   |    |           |
red red blue yellow blue yellow
                 |           |
                 +-----------+

Chiều cao tối thiểu là 2 trong trường hợp này.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\).
\(T\) bộ test tiếp theo. Dòng đầu tiên của mỗi bộ test chứa \(n\), số lượng màu khác nhau của các viên bi. Dòng tiếp theo chứa một chuỗi gồm \(2n\) từ cách nhau bởi dấu cách, tương ứng với màu sắc của các viên bi, theo thứ tự từ trái sang phải. Mỗi màu là một chuỗi các chữ cái tiếng Anh viết thường ('a' .. 'z') dài không quá 10 ký tự. Sẽ có đúng \(n\) màu khác nhau và mỗi màu sẽ xuất hiện đúng hai lần.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #\(x\): ", trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), tiếp theo là chiều cao của bất kỳ giải pháp tối ưu nào, hoặc -1 nếu không tồn tại giải pháp.

Ràng buộc

• \(1 \le T \le 50\).

Phân nhóm

• Small dataset: \(1 \le n \le 20\).
• Large dataset: \(1 \le n \le 500\).

Đ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
3
red red blue yellow blue yellow
3
red blue yellow red blue yellow
3
red blue yellow blue yellow red
3
red red blue blue yellow yellow

Case #1: 2
Case #2: -1
Case #3: 3
Case #4: 1

Nguồn

Google Code Jam 2009, Chung kết thế giới, bài Marbles.

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