Bitonic Tour

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

Start at vertex $1$, visit vertices in strictly increasing order until reaching $N$, and then visit vertices in strictly decreasing order before returning to $1$. Before returning to the start, you must visit every vertex exactly once, and every edge used must exist. Find any valid visiting order with minimum total edge weight.

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 visiting order exists.

Otherwise, print its minimum total weight on the first line and the vertex numbers $p_1,p_2,\ldots,p_N$ visited before returning to the start on the second line, separated by spaces. Here $p_1=1$, and $p_1,p_2,\ldots,p_N$ is a permutation of $1$ through $N$. Include the edge from $p_N$ back to $1$ in the total weight. If several answers exist, print any of them.

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