Bạn đang chơi một trò solitaire với \(N\) chồng bài ngửa, ban đầu mỗi chồng có \(C\) lá. Mỗi lá có một giá trị và một chất; không có hai lá nào trong cùng ván mang cùng cặp giá trị/chất.

Trong một nước đi, bạn được làm đúng một trong hai việc:

• Nếu trên đỉnh các chồng khác nhau có ít nhất hai lá cùng chất, bỏ khỏi ván lá có giá trị nhỏ nhất trong số các lá ấy. Khi bỏ lá cuối cùng, chồng vẫn tồn tại nhưng trở thành chồng rỗng.
• Nếu có một chồng rỗng, lấy lá trên đỉnh của một chồng không rỗng bất kỳ và đặt nó lên chồng rỗng (khi đó nó là lá duy nhất trong chồng ấy).

Bạn thắng nếu có thể thực hiện một dãy nước đi để cuối cùng mỗi chồng chứa nhiều nhất một lá. Hãy xác định có thể thắng từ cách xếp ban đầu hay không.

Dữ liệu vào

Dòng đầu chứa số chồng dựng sẵn \(P\) dùng trong các test. Sau đó là \(P\) dòng. Dòng thứ \(i\) bắt đầu bằng \(C_i\), số lá của chồng dựng sẵn thứ \(i\), rồi đến \(C_i\) cặp số \((V_{ij},S_{ij})\). Cặp thứ \(j\) cho giá trị và chất của lá thứ \(j\) tính từ đỉnh xuống.

Tiếp theo là một dòng chứa số test \(T\). Mỗi test bắt đầu bằng \(N,C\), lần lượt là số chồng và số lá trong mỗi chồng của test. Dòng sau chứa \(N\) chỉ số \(P_i\) (đánh số từ 0), chỉ ra các chồng dựng sẵn được dùng.

Dữ liệu ra

Với mỗi test, in Case #x: y, trong đó x là số thứ tự test bắt đầu từ 1 và y là POSSIBLE nếu có thể thắng, hoặc IMPOSSIBLE nếu không thể.

Ràng buộc

• \(1\le T\le100\).
• \(2\le P\le60000\).
• \(0\le P_i<P\).
• Chồng dựng sẵn thứ \(P_i\) có đúng \(C\) lá.
• Không có hai lá trong một test mang cùng cặp giá trị/chất.

Phân nhóm

• Test Set 1 (Visible): \(2\le N\le4\); \(2\le C_i\le13\); \(2\le C\le13\); \(1\le V_{ij}\le13\); \(1\le S_{ij}\le4\).
• Test Set 2 (Hidden): \(2\le N\le50000\); \(2\le C_i\le50000\); \(2\le C\le50000\); \(4\le N\times C\le10^5\); \(1\le V_{ij},S_{ij}\le50000\).

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

5
2 7 2 7 1
2 6 4 7 4
2 3 2 6 2
2 4 2 10 2
2 5 4 7 3
2
2 2
0 2
3 2
4 1 3

Case #1: POSSIBLE
Case #2: IMPOSSIBLE

Nguồn

Google Code Jam 2017, Chung kết thế giới, bài Stack Management.

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