Задачі
Продавець акваріумів
Продавець акваріумів
Продавець акваріумів для котів хоче об'їехати n міст, відвідавши кожне з них рівно один раз. Допоможіть йому знайти найкоротший шлях.
Вхідні дані
Перший рядок вхідного файлу містить натуральне число 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).
Вихідні дані
У першому рядку вихідного файлу виведіть довжину найкоротшого шляху. У другому рядку виведіть n чисел - порядок, у якому потрібно відвідати міста.
Приклад
Вхідні дані #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
Вихідні дані #1
666 4 5 2 3 1