Shota là một nông dân và anh ấy đang gặp vấn đề. Anh ấy vừa chuyển đến một trang trại mới xây, nhưng hóa ra các ổ cắm điện không được cấu hình đúng cho tất cả các thiết bị của anh ấy. Là một nông dân hiện đại, Shota sở hữu rất nhiều điện thoại thông minh, máy tính xách tay và thậm chí cả một chiếc máy tính bảng cho con bò Wagyu yêu thích của mình. Tổng cộng, anh ấy có \(N\) thiết bị khác nhau.

Vì các thiết bị này có thông số kỹ thuật khác nhau và được sản xuất bởi nhiều công ty khác nhau, mỗi thiết bị yêu cầu một dòng điện khác nhau để sạc. Tương tự, mỗi ổ cắm trong nhà cung cấp một dòng điện cụ thể. Một dòng điện có thể được biểu diễn bằng một chuỗi các ký tự 0 và 1 có độ dài \(L\).

Shota muốn có thể sạc tất cả \(N\) thiết bị của mình cùng một lúc. Thật trùng hợp, có đúng \(N\) ổ cắm trong ngôi nhà mới của anh ấy. Để cấu hình dòng điện từ các ổ cắm, có một bảng điều khiển trung tâm với \(L\) công tắc. Công tắc thứ \(i\) sẽ đảo ngược bit thứ \(i\) của dòng điện từ mọi ổ cắm trong nhà. Ví dụ, nếu dòng điện từ các ổ cắm là:

Outlet 0: 10
Outlet 1: 01
Outlet 2: 11

Thì việc bật công tắc thứ hai sẽ cấu hình lại dòng điện thành:

Outlet 0: 11
Outlet 1: 00
Outlet 2: 10

Nếu Shota có một chiếc điện thoại thông minh cần dòng điện 11 để sạc, một chiếc máy tính bảng cần dòng điện 10 và một chiếc máy tính xách tay cần dòng điện 00, thì việc bật công tắc thứ hai sẽ khiến anh ấy rất hạnh phúc!

Misaki đã được Shota thuê để giúp giải quyết vấn đề này. Cô ấy đã đo dòng điện từ các ổ cắm trong nhà và nhận thấy rằng chúng đều khác nhau. Hãy quyết định xem Shota có thể sạc tất cả các thiết bị của mình cùng một lúc hay không, và nếu có thể, hãy tìm số lượng công tắc tối thiểu cần phải bật, vì các công tắc này rất lớn và nặng, Misaki không muốn bật nhiều hơn mức cần thiế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ộ thử nghiệm, \(T\). Tiếp theo là \(T\) bộ thử nghiệm. Mỗi bộ thử nghiệm gồm ba dòng:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(L\) cách nhau bởi dấu cách.
• Dòng thứ hai chứa \(N\) chuỗi độ dài \(L\) cách nhau bởi dấu cách, đại diện cho dòng điện ban đầu từ các ổ cắm.
• Dòng thứ ba cũng chứa \(N\) chuỗi độ dài \(L\) cách nhau bởi dấu cách, đại diện cho dòng điện yêu cầu bởi các thiết bị của Shota.

Dữ liệu ra

Với mỗi bộ thử nghiệm, xuất một dòng chứa Case #x: y, trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là số lượng công tắc tối thiểu cần bật để Shota có thể sạc tất cả các thiết bị của mình. Nếu không thể, y phải là chuỗi NOT POSSIBLE. Lưu ý rằng giám khảo không phân biệt chữ hoa chữ thường cho chuỗi này, nhưng chúng tôi khuyên bạn nên sao chép đúng chuỗi NOT POSSIBLE.

Ràng buộc

• \(1 \le T \le 100\).
• Ban đầu, không có hai ổ cắm nào có cùng dòng điện.
• Không có hai thiết bị nào yêu cầu cùng một dòng điện.

Phân nhóm

• Small dataset: \(1 \le N \le 10\); \(2 \le L \le 10\).
• Large dataset: \(1 \le N \le 150\); \(10 \le L \le 40\).

Đ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 2
01 11 10
11 00 10
2 3
101 111
010 001
2 2
01 10
10 01

Case #1: 1
Case #2: NOT POSSIBLE
Case #3: 0

Outlet 0: 00
Outlet 1: 10
Outlet 2: 11

Nguồn

Google Code Jam 2014, Vòng 1A, bài Charging Chaos.

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