SCIENCE - 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 Olympian, figure out how many times we can do this. And make it quick, we have a lot more science to get through.

Input

The first line will contain N (2 ≤ N ≤ 200) 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.

Output

If it is impossible to get everyone on the buttons at once output "NO SCIENCE" (quotes for clarity). Otherwise first output K, the maximum number of times everyone can be standing on buttons such that nobody stands on the same button more than once. After that output K lines. Each line should contain N integers separated by a space where the ith integer describes who is on the ith button. All of the lines should be valid and none of them should put the same person on the same button.  If there are multiple solutions, output any of them.

Examples

Input:
3
YYY
NYY
YNY Output: 2
1 2 3
3 1 2
Input:
2
YN
YN Output: NO SCIENCE

Added by:Mark Gordon
Date:2013-04-02
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:2012 University of Chicago Invitational Contest (but with harder constraints)

hide comments
2015-02-02 16:31:07 Mark Gordon
@Wesley: Yes, it appeared in Chicago's 2012 (I've listed it now). This version has larger constraints and is significantly harder, though. (Also, I am the original author of this problem)

Edit Again: I was speaking to rpeng about this problem and he helped me recall that it was never actually used in the Michigan contest. The Chicago contest was the only contest it has been in.

Last edit: 2013-06-05 22:35:34
2015-02-02 16:31:07 Wesley May
This problem is from the 2012 University of Chicago Invitational Contest (http://icpc.cs.uchicago.edu/invitational2012/_static/ucipc2012-problems.pdf)
2015-02-02 16:31:07 Mark Gordon
Any solution is accepted by a custom judge. Your example would get AC.
2015-02-02 16:31:07 Francky
Is there any order for the answers, or any order is accepted by a custum judge ?
For first input, is
2
3 1 2
1 2 3
getting AC too ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.