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^{6}.

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.

Public test cases

**Input**

3 0 7 3 9 0 2 9 8 0

**Output**

1 2 3 1 3 2 min: 9

**Input**

2 0 1000000 1 0

**Output**

1 2 min: 1000000

**Input**

5 0 2 0 2 1 0 0 2 0 2 0 1 0 2 2 0 2 1 0 2 0 0 2 1 0

**Output**

1 2 3 4 5 1 2 3 5 4 1 2 5 3 4 1 2 5 4 3 1 4 2 3 5 1 4 2 5 3 1 4 3 2 5 1 4 5 3 2 1 5 3 4 2 1 5 4 2 3 1 5 4 3 2 min: 4

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++