외판원 순회 문제

정점이 $N$개인 가중치 방향 그래프가 주어진다. 정점 $i$에서 정점 $j$로 가는 간선의 가중치는 $W_{ij}$이다. $W_{ij}=-1$이면 해당 간선은 없다.

$1$부터 $N$까지의 정점을 어떤 순서로 나열한 뒤, 나열한 순서대로 간선을 따라 이동하고 마지막 정점에서 첫 정점으로 돌아오려 한다. 이때 모든 이동에 해당하는 간선이 존재해야 한다. 가능한 순서 중 지나간 간선의 가중치 합이 최소인 것을 아무거나 하나 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

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

각 케이스마다 조건을 만족하는 순서가 없으면 $-1$만 출력한다.

그렇지 않으면 첫째 줄에 최소 총 가중치를 출력하고, 둘째 줄에 정점을 방문하는 순서 $p_1,p_2,\ldots,p_N$을 공백으로 구분하여 출력한다. $p_1,p_2,\ldots,p_N$은 $1$부터 $N$까지의 순열이며, $p_N$에서 $p_1$로 돌아가는 간선도 총 가중치에 포함된다. 가능한 답이 여러 개라면 아무거나 출력해도 된다.

• $1\leq T\leq5000$.
• $2\leq N\leq18$.
• $-1\leq W_{ij}\leq10^9$이며, $-1$은 간선이 없음을 뜻한다.
• $W_{ii}=0$이다.
• 모든 케이스에 대한 $N^2$의 합은 $40\,000$ 이하이다.
• 모든 케이스에 대한 $N^2 2^N$의 합은 $100\,000\,000$ 이하이다.