Problems
Продавец аквариумов
Продавец аквариумов
Продавец аквариумов для кошек хочет объехать n городов, посетив каждый из них ровно один раз. Помогите ему найти кратчайший путь.
Input data
Первая строка входного файла содержит натуральное число n (1 ≤ n ≤ 13) - количество городов. Следующие nстрок содержат n чисел - длины путей между городами.
В i-ой строке j-ое число, a_{i,j} - это расстояние между городами i и j (0 ≤ a_{i,j} ≤ 10^6, a_{i,j} = a_{j,i}, a_{i,i} = 0).
Output data
В первой строке выходного файла выведите длину кратчайшего пути. Во второй стороке выведите n чисел - порядок, в котором нужно посетить города.
Examples
Input example #1
5 0 183 163 173 181 183 0 165 172 171 163 165 0 189 302 173 172 189 0 167 181 171 302 167 0
Output example #1
666 4 5 2 3 1