eolymp
bolt
Try our new interface for solving problems
Problems

Продавец аквариумов

Продавец аквариумов

Time limit 1 second
Memory limit 64 MiB

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

Input data

Первая строка входного файла содержит натуральное число 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).

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