Торгівцю необхідно відвідати \(N\) міст, кожне по одному разу. Знайдіть найкоротший шлях.

Формат вхідних даних

В першому рядку число \(N\) - кількість міст (\(1 \le N \le 20\))
Кожен з наступних \(N\) рядків містить по \(N\) цілих чисел - відстані між відповідними містами.
В i-му рядку j-те число \(Aij\) - це відстань між містами \(i\) та \(j\) (\(0 \le Aij \le 10^6, Aij=Aji, Aii=0\))

Формат вихідних даних

В першому рядку виведіть - довжину найкоротшого шляху.
В наступному рядку виведіть номера міст в порядку обходу. (якщо є кілька шляхів мінімальної довжини, виведіть будь-який з них)

Приклад вхідних даних

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

Приклад вихідних даних

666
1 3 2 5 4