역설 정렬

Vlad는 사탕을 좋아한다. 서로 다른 사탕이 든 가방이 있고, 그중 하나를 Vlad가 가지게 하려고 한다. 사탕의 순서를 정한 다음, Vlad에게 하나씩 건넨다. Vlad는 사탕을 받을 때마다(첫 번째 사탕 이후), 가지고 있던 사탕과 방금 받은 사탕을 비교하여 더 좋아하는 것을 가지고 나머지 하나는 버린다.

어떤 순서를 선택하더라도 Vlad가 항상 가장 좋아하는 사탕을 최종적으로 가지게 될 것이라고 예상할 수 있다. 하지만 그렇지 않다! Vlad에게는 반드시 가장 좋아하는 사탕이 있는 것이 아니다. 임의의 사탕 한 쌍에 대해 그가 어느 것을 더 선호할지는 알지만, 그의 선택이 반드시 단순한 순위와 일치하지는 않는다. Orange와 Lemon이 주어지면 Orange를, Orange와 Banana가 주어지면 Banana를, Lemon과 Banana가 주어지면 Lemon을 선택할 수도 있다!

Vlad가 최종적으로 가지게 하고 싶은 특정 사탕이 있다. 각 사탕 쌍에 대한 Vlad의 선호가 주어질 때, Vlad가 원하는 사탕을 최종적으로 가지게 되는 순서가 존재하는지 판별한다. 존재한다면, 그러한 순서 중 사전순으로 가장 작은 것을 구한다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100.

소규모 데이터셋

시간 제한: 60초. 1 ≤ N ≤ 10.

대규모 데이터셋

시간 제한: 120초. 1 ≤ N ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 공백으로 구분된 정수 N과 A가 포함된 줄로 시작한다. N은 사탕의 수이고, A는 Vlad가 마지막에 가지기를 원하는 사탕의 번호이다. 사탕에는 0부터 N-1까지 번호가 매겨져 있다. 다음 N개의 줄에는 각각 N개의 문자가 포함된다. i번째 줄의 j번째 문자는 Vlad가 사탕 i를 사탕 j보다 선호하면 'Y', 사탕 j를 사탕 i보다 선호하면 'N', i = j이면 '-'이다. i ≠ j이면 i번째 행의 j번째 문자와 j번째 행의 i번째 문자는 서로 달라야 한다는 점에 유의한다.

각 테스트 케이스마다 "Case #x: "을 출력한다. 여기서 x는 케이스 번호이며, 그 뒤에 "IMPOSSIBLE" 또는 Vlad가 A를 최종적으로 가지게 하는 사탕 순서 중 사전순으로 가장 작은 것을 공백으로 구분한 목록을 출력한다.