Bạn sở hữu một cửa hàng sữa lắc. Có \(N\) hương vị khác nhau mà bạn có thể chuẩn bị, và mỗi hương vị có thể được chế biến theo kiểu "malted" (có mạch nha) hoặc "unmalted" (không có mạch nha). Vì vậy, bạn có thể tạo ra \(2N\) loại sữa lắc khác nhau.

Mỗi khách hàng của bạn có một tập hợp các loại sữa lắc mà họ thích, và họ sẽ hài lòng nếu bạn chuẩn bị ít nhất một trong những loại đó. Trong số các loại mà một khách hàng thích, có tối đa một loại là hương vị "malted".

Bạn muốn tạo ra \(N\) mẻ sữa lắc sao cho:

• Có đúng một mẻ cho mỗi hương vị sữa lắc, và nó là malted hoặc unmalted.
• Đối với mỗi khách hàng, bạn tạo ra ít nhất một loại sữa lắc mà họ thích.
• Số lượng mẻ sữa lắc malted là ít nhất có thể.

Hãy tìm xem có thể làm hài lòng tất cả khách hàng của bạn với những ràng buộc này hay không, và nếu có, bạn nên làm những loại sữa lắc nào.

Nếu có thể làm hài lòng tất cả khách hàng, sẽ chỉ có duy nhất một đáp án tối thiểu hóa số lượng mẻ malted.

Dữ liệu vào

• Một dòng chứa số nguyên \(C\), số lượng bộ dữ liệu trong tệp đầu vào.
• Đối với mỗi bộ dữ liệu:
  • Một dòng chứa số nguyên \(N\), số lượng hương vị sữa lắc.
  • Một dòng chứa số nguyên \(M\), số lượng khách hàng.
  • \(M\) dòng, mỗi dòng cho một khách hàng, chứa:
    • Một số nguyên \(T \ge 1\), số lượng loại sữa lắc khách hàng thích, theo sau bởi
    • \(T\) cặp số nguyên "\(X\) \(Y\)", mỗi cặp cho một loại khách hàng thích, trong đó \(X\) là hương vị sữa lắc từ \(1\) đến \(N\), kể cả hai đầu, và \(Y\) là 0 để chỉ unmalted, hoặc 1 để chỉ malted.
    • Lưu ý:
      • Không có cặp nào xuất hiện nhiều hơn một lần cho cùng một khách hàng.
      • Mỗi khách hàng sẽ thích ít nhất một hương vị (\(T \ge 1\)).
      • Mỗi khách hàng sẽ thích tối đa một hương vị malted (tối đa một cặp cho mỗi khách hàng có \(Y = 1\)).

Tất cả các số này được phân tách bằng các khoảng trắng đơn.

Dữ liệu ra

\(C\) dòng, mỗi dòng cho một bộ dữ liệu theo thứ tự xuất hiện trong tệp đầu vào, mỗi dòng chứa chuỗi "Case #\(X\): " trong đó \(X\) là số thứ tự của bộ dữ liệu, bắt đầu từ 1, tiếp theo là:

• Chuỗi "IMPOSSIBLE", nếu không thể thỏa mãn sở thích của các khách hàng; HOẶC
• \(N\) số nguyên cách nhau bởi khoảng trắng, mỗi số cho một hương vị từ \(1\) đến \(N\), là 0 nếu hương vị tương ứng nên được chuẩn bị unmalted, và 1 nếu là malted.

Ràng buộc

Phân nhóm

• Small dataset (Test set 1):
  • \(C = 100\)
  • \(1 \le N \le 10\)
  • \(1 \le M \le 100\)
• Large dataset (Test set 2):
  • \(C = 5\)
  • \(1 \le N \le 2000\)
  • \(1 \le M \le 2000\)
  • Tổng của tất cả các giá trị \(T\) cho các khách hàng trong một bộ dữ liệu sẽ không vượt quá 3000.

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

2
5
3
1 1 1
2 1 0 2 0
1 5 0
1
2
1 1 0
1 1 1

Case #1: 1 0 0 0 0
Case #2: IMPOSSIBLE

Nguồn

Google Code Jam 2008, Vòng 1A, bài Milkshakes.

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