[placeholder] rất lười vận động. Cậu suốt ngày ngồi ở nhà chơi điện tử. Một ngày, mẹ của [placeholder] rút dây máy tính, và bắt cậu ra ngoài đi dạo 1 vòng.
Nhà của [placeholder] nằm ở đỉnh ~1~ trong một đồ thị đầy đủ có hướng gồm ~n~ đỉnh. Các cạnh của đồ thị có trọng số. [placeholder] muốn tìm đi thăm ~k-1~ người bạn. Vì rất lười nên [placeholder] muốn chuyến đi dạo ngắn nhất có thể.
Bạn hãy giúp [placeholder] tìm một chu trình đơn giản có độ dài ~k~ có tổng trọng số các cạnh là nhỏ nhất.
Input
Dòng đầu tiên chứa 2 số ~n~, ~k~, số đỉnh của đồ thị và độ dài chu trình cần tìm (~n \le 50~, ~k \le min(n, 8), k~ chẵn).
~n~ dòng tiếp theo, mỗi dòng chứa ~n~ số ~a_{i,j}~, độ dài cạnh từ đỉnh ~i~ đến đỉnh ~j~ (~1 \le a_{i,j} \le 100000, a_{i,i} = 0~)
Output
Dòng đầu chứa số ~s~ - độ dài của chu trình ngắn nhất. Dòng tiếp theo chứa ~k~ số - các đỉnh trên chu trình. Đỉnh đầu tiên của chu trình phải là đỉnh ~1~.
Sample Input 1
5 4
0 2 5 4 2
9 0 5 3 7
1 6 0 4 3
9 7 8 0 5
1 5 7 3 0
Sample Output 1
11
1 2 3 5
Bình luận