#603 tsp

Statement

Statement language

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.

Input

The input is given in the following format:

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

Output

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 through . Include the edge from back to in the total weight. If several answers exist, print any of them.

Constraints

$1\leq T\leq5000$ .
$2\leq N\leq18$ .
$-1\leq W_{ij}\leq10^9$ , where means that the edge does not exist.

Subtasks

#	Score	Constraints
1	20	$N\leq8$ . The sum of $N^2$ over all cases is at most $10\,000$ .
2	80	No additional constraints.

Samples

Input

Output

9
1 2 3
-1