Problem F

Welcome, ladies and gentlemen, to Aperture Science. Astronauts, War Heroes, Olympians — you’re here because we want the best, and you are it. That said, it’s time to make some science.

Now, I want each of you to stand on one of these buttons. Well done, we’re making great progress here. Now let’s do it again. Oh, come on - don’t stand on the same button! Move, people! No, no, that button’s only for the Astronauts, you know who you are. What?! You say you can’t do everything I ask? Ok let’s start over. You there, the Programmer, figure out how many times we can do this. And make it quick, we have a lot more science to get through…


There will be a single test case in the input. The first line of this case will contain $n$ ($2 \le n \le 80$) giving the number of people (and the number of buttons) in the experiment. The next $n$ lines will contain $n$ characters each. If the $j^{th}$ character of the $i^{th}$ line is Y it indicates that the $i^{th}$ person can stand on the $j^{th}$ button (it is N otherwise).


Output $k$, the maximum number of times everyone can be standing on buttons such that nobody stands on the same button more than once (This might be $0$). After that, output $k$ lines. Each line should contain $n$ integers separated by single spaces, where the $i^{th}$ integer describes which person is standing on the $i^{th}$ button. All of the lines should be valid and none of them should put the same person on the same button as a previous line of the same test case. Note that correct outputs might not be unique.

Sample Input 1 Sample Output 1
1 2 3
3 1 2
Sample Input 2 Sample Output 2

Please log in to submit a solution to this problem

Log in