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.

Public test cases

**Input**

2 0 5 7 0 3 0 1 2 3 0 4 5 6 0 4 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 5 0 0 20 30 0 0 0 10 50 60 90 80 0 0 70 40 0 25 0 95 15 10 75 35 0

**Output**

0 1 0 (12) -------------------- 0 1 2 0 (10) 0 2 1 0 (11) -------------------- 0 1 2 3 0 (4) 0 1 3 2 0 (4) 0 2 1 3 0 (4) 0 2 3 1 0 (4) 0 3 1 2 0 (4) 0 3 2 1 0 (4) -------------------- 0 2 1 3 4 0 (260) 0 2 1 4 3 0 (235) 0 2 4 1 3 0 (190) 0 3 2 1 4 0 (210) 0 3 4 1 2 0 (235) --------------------

Information

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