tsp

You are given a weighted directed graph with $N$ vertices. The weight of the edge from vertex $i$ to vertex $j$ is $W_{ij}$. If $W_{ij}=-1$, that edge does not exist.

Arrange all vertices in some order, follow the directed edges between consecutive vertices, and return from the last vertex to the first. Every edge used must exist. Find any such order that minimizes the sum of the weights of these edges.

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N$ $W_{11}\ W_{12}\ \cdots\ W_{1N}$ $W_{21}\ W_{22}\ \cdots\ W_{2N}$ $\vdots$ $W_{N1}\ W_{N2}\ \cdots\ W_{NN}$

For each case, print only $-1$ if no valid order exists.

Otherwise, print its minimum total weight on the first line and the vertex numbers $p_1,p_2,\ldots,p_N$ on the second line, separated by spaces. The vertices must form a permutation of $1$ through $N$. Include the edge from $p_N$ back to $p_1$ in the total weight. If several answers exist, print any of them.

• $1\leq T\leq5000$.
• $2\leq N\leq18$.
• $-1\leq W_{ij}\leq10^9$, where $-1$ means that the edge does not exist.
• $W_{ii}=0$.
• The sum of $N^2$ over all cases is at most $40\,000$.
• The sum of $N^2 2^N$ over all cases is at most $100\,000\,000$.