eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Продавець акваріумів

Продавець акваріумів

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Продавець акваріумів для котів хоче об'їехати n міст, відвідавши кожне з них рівно один раз. Допоможіть йому знайти найкоротший шлях.

Вхідні дані

Перший рядок вхідного файлу містить натуральне число n (1n13) - кількість міст. Наступні n рядків містять n чисел - довжини шляхів між містами.

У i-ому рядку j-те число, a_{i,j} - це відстань між містами i та j (0a_{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