Hamiltonian paths P56416

Given a directed graph with arcs with positive costs, print all the paths that begin at the first vertex and visit all vertices exactly once. Moreover, compute the minimum of the costs of these paths.

Input

Input consists of the number of vertices n, followed by n rows with n natural numbers each. The j-th number of the i-th row indicates the cost of the arc going from vertex i to vertex j. A zero cost indicates a missing arc (the diagonal has only zeros). Assume 2 ≤ n ≤ 15, and that all costs are between 1 and 10⁶.

Output

Print, in lexicographical order, print all the paths that begin at the first vertex and visit all vertices exactly once. Afterwards, print the minimum cost of all these paths. There will always be at least one path.