Theo một bản đồ cũ, bạn đã tình cờ tìm thấy kho báu bí mật của Cướp biển Larry Đáng sợ!

Kho báu bao gồm \(N\) chiếc rương bị khóa, mỗi chiếc chỉ có thể được mở bằng một loại chìa khóa cụ thể. Hơn nữa, một khi chìa khóa đã được sử dụng để mở rương, nó sẽ không bao giờ có thể được sử dụng lại. Bên trong mỗi chiếc rương, tất nhiên bạn sẽ tìm thấy rất nhiều kho báu, và bạn cũng có thể tìm thấy một hoặc nhiều chìa khóa mà bạn có thể sử dụng để mở các rương khác. Một chiếc rương có thể chứa nhiều chìa khóa cùng loại, và bạn có thể giữ bất kỳ số lượng chìa khóa nào.

Bạn đã có sẵn ít nhất một chiếc chìa khóa và bản đồ của bạn cho biết những chiếc chìa khóa nào khác có thể được tìm thấy bên trong các rương khác nhau. Với tất cả thông tin này, bạn có thể tìm ra cách mở tất cả các rương không?

Ví dụ, giả sử kho báu bao gồm bốn chiếc rương như mô tả dưới đây, và bạn bắt đầu với chính xác một chiếc chìa khóa loại 1:

Chest Number  |  Key Type To Open Chest  |  Key Types Inside
--------------+--------------------------+------------------
1             |  1                       |  None
2             |  1                       |  1, 3
3             |  2                       |  None
4             |  3                       |  2

Bạn có thể mở tất cả các rương trong ví dụ này nếu bạn thực hiện chúng theo thứ tự 2, 1, 4, 3. Nếu bạn bắt đầu bằng cách mở rương số 1 trước, thì bạn sẽ dùng hết chiếc chìa khóa duy nhất của mình và bạn sẽ bị kẹt.

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. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên dương \(K\) và \(N\), đại diện cho số lượng chìa khóa bạn có lúc đầu và số lượng rương bạn cần mở.

Tiếp theo là một dòng chứa \(K\) số nguyên, đại diện cho các loại chìa khóa mà bạn có lúc đầu.

Sau đó, sẽ có \(N\) dòng, mỗi dòng đại diện cho một chiếc rương duy nhất. Mỗi dòng sẽ bắt đầu bằng các số nguyên \(T_i\) và \(K_i\), cho biết loại chìa khóa cần thiết để mở rương và số lượng chìa khóa bên trong rương. Hai số nguyên này sẽ được theo sau bởi \(K_i\) số nguyên nữa, cho biết các loại chìa khóa có trong rương đó.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: \(C_1\) \(C_2\) ... \(C_N\)", trong đó x là số thứ tự bộ test (bắt đầu từ 1), và \(C_i\) đại diện cho chỉ số (bắt đầu từ 1) của chiếc rương thứ \(i\) mà bạn nên mở.

Nếu có nhiều cách mở tất cả các rương, hãy chọn cách "nhỏ nhất về mặt từ điển". Nói cách khác, bạn nên chọn làm cho \(C_1\) nhỏ nhất có thể, và nếu có nhiều cách để làm cho \(C_1\) nhỏ nhất có thể, hãy chọn cách làm cho \(C_2\) nhỏ nhất có thể, và cứ tiếp tục như vậy.

Nếu không có cách nào để mở tất cả các rương, thay vào đó bạn nên xuất một dòng chứa "Case #x: IMPOSSIBLE".

Ràng buộc

• \(1 \le T \le 25\).
• \(1 \le K\).
• Tất cả các loại chìa khóa sẽ là các số nguyên từ 1 đến 200 bao gồm cả hai đầu.

Phân nhóm

• Small dataset (Test set 1): \(1 \le N \le 20\). Trong mỗi bộ test, sẽ có tổng cộng tối đa 40 chìa khóa.
• Large dataset (Test set 2): \(1 \le N \le 200\). Trong mỗi bộ test, sẽ có tổng cộng tối đa 400 chìa khóa.

Đ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
1 4
1
1 0
1 2 1 3
2 0
3 1 2
3 3
1 1 1
1 0
1 0
1 0
1 1
2
1 1 1

Case #1: 2 1 4 3
Case #2: 1 2 3
Case #3: IMPOSSIBLE

Nguồn

Google Code Jam 2013, Vòng loại, bài Treasure.

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