All submissions for this problem are available.

Politics

Leaders of N political parties agree to have a conference to resolve a political issue through discussion. However due to animosity between parties and leaders, some of the leaders may dislike sitting next to leaders specified by them. The problem is to determine, if possible, sitting arrangements on the table, so that a leader is not required to sit next to another leader disliked by him/her. Leaders are identified by integers 1,2,..,N. It may be noted that if a leader i dislikes sitting next to another leader j , then the leader j may not necessarily dislike sitting next to leader i . However in such a case i and j cannot sit next to each other because i dislikes j .

An arrangement is represented by a sequence of N integers 1,2, ,N indicating the relative position of each leader. In case of more than one arrangement, the arrangements are to be printed in lexicographic order.

Write a program to print all possible sitting arrangements for the conference.

Input:

The input may contain multiple test cases. The first line of each test case contains the case number c and the total number of leaders N where N will be less than 100. Each of the next N lines contains N 0 s or 1 s. If the value in i^th row and j^th column contains 1, then the i^th leader cannot sit with j^th leader. This is true for all I,j=1,2, ,N. The input terminates with a single 0 in the last line.

Output:

For each test case, print the case number c and the total number of possible arrangements k in first line with a single space between them. Each of the next k lines prints an arrangements in lexicographical order separated with a single space.

Sample Input

1 5

11010

01001

00100

10010

01011

2 6

101100

010001

101000

100110

001011

010011

0

Sample Output

1 0

2 2

1 5 2 3 4 6

1 5 2 4 3 6