Vlad rất thích kẹo. Bạn có một túi đựng các loại kẹo khác nhau và bạn định cho Vlad giữ lại một trong số chúng. Bạn chọn một thứ tự cho các viên kẹo, sau đó đưa từng viên một cho Vlad. Đối với mỗi viên kẹo Vlad nhận được (sau viên đầu tiên), anh ấy sẽ so sánh viên kẹo đang giữ với viên kẹo vừa được đưa, giữ lại viên anh ấy thích hơn và vứt viên còn lại đi.

Bạn có thể kỳ vọng rằng với bất kỳ thứ tự nào bạn chọn, Vlad sẽ luôn giữ lại viên kẹo yêu thích nhất của anh ấy. Nhưng thực tế không phải vậy! Anh ấy không nhất thiết phải có một viên kẹo yêu thích nhất duy nhất. Chúng ta biết với bất kỳ cặp kẹo nào, anh ấy sẽ thích viên nào hơn, nhưng lựa chọn của anh ấy không nhất thiết tuân theo một thứ hạng đơn giản. Anh ấy có thể chọn Cam khi được đưa Cam và Chanh, chọn Chuối khi được đưa Cam và Chuối, và chọn Chanh khi được đưa Chanh và Chuối!

Có một viên kẹo cụ thể mà bạn muốn Vlad giữ lại cuối cùng. Cho biết sở thích của Vlad đối với từng cặp kẹo, hãy xác định xem có thứ tự nào để Vlad giữ lại đúng viên kẹo đó hay không. Nếu có, hãy tìm thứ tự có thứ tự từ điển nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ dữ liệu, \(T\). \(T\) bộ dữ liệu tiếp theo. Mỗi bộ dữ liệu bắt đầu bằng một dòng chứa các số nguyên \(N\) và \(A\), cách nhau bởi một dấu cách. \(N\) là số lượng kẹo, và \(A\) là số hiệu của viên kẹo mà chúng ta muốn Vlad giữ lại cuối cùng. Các viên kẹo được đánh số từ \(0\) đến \(N-1\). \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) ký tự. Ký tự thứ \(j\) của dòng thứ \(i\) sẽ là 'Y' nếu Vlad thích kẹo \(i\) hơn kẹo \(j\), 'N' nếu Vlad thích kẹo \(j\) hơn kẹo \(i\), và '-' nếu \(i = j\). Lưu ý rằng nếu \(i \neq j\), ký tự thứ \(j\) của hàng thứ \(i\) phải khác với ký tự thứ \(i\) của hàng thứ \(j\).

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra "Case #x: ", trong đó x là số thứ tự bộ dữ liệu, tiếp theo là "IMPOSSIBLE" hoặc một danh sách các số hiệu kẹo cách nhau bởi dấu cách, đại diện cho thứ tự có thứ tự từ điển nhỏ nhất khiến Vlad giữ lại kẹo \(A\).

Ràng buộc

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

Phân nhóm

• Small dataset: \(1 \le N \le 10\).
• Large dataset: \(1 \le N \le 100\).

Đ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
2 0
-Y
N-
2 0
-N
Y-
4 3
-YNN
N-YY
YN-Y
YNN-

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

Nguồn

Google Code Jam 2014, Chung kết thế giới, bài Paradox Sort.

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