4794번 - Science! 스페셜 저지다국어

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 several test cases in the input. The first line of each case will contain n (2≤n≤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 jth character of the ith line is Y it indicates that the ith person can stand on the jth button (it is N otherwise). The last line of input will be a 0.

For each test case, 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 ith integer describes which person is standing on the ith 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. Output no extra spaces, and do not separate answers with blank lines. Note that correct outputs might not be unique