All hamiltonian cycles P16553

Given a directed graph with arcs with positive costs, print all paths that leave the first vertex, end in the first vertex, and pass through all other vertices exactly once. Also, print the cost of each of these cycles.

Input

Input consists of several cases. Every case starts with the number of vertices n followed by n rows, each with n numbers. The j-th number of the i-th row indicates the cost of the arc going from vertex i to vertex j (vertices are numbered from 0 to n − 1). A cost equal to zero indicates that there is no arc (the diagonal has only zeros). Assume that n is “small” and at least 2, and that the cost of each cycle fits into an integer number.

Output

Print, in lexicographical order, all cycles of length n that leave and end at vertex 0 without repeating vertices, and the cost of each cycle. Print a line with 20 dashes at the end of each case.