Гамільтонів цикл#1680
Граф Вільям Гамільтон вирішив вирушити у подорож та відвідати найбільших міст на Землі. Кожна пара міст з'єднана дорогою. Кожна дорога має значення видовищності, яке є ступенем числа . Значення видовищності дороги може відрізнятися залежно від напрямку руху, і всі значення видовищності унікальні. Граф хоче вибрати замкнений маршрут, який починається і закінчується в одному місті, проходить через кожне місто рівно один раз і максимізує загальну видовищність.
Напишіть програму, яка визначить оптимальний замкнений маршрут для графа Гамільтона.
Перший рядок містить (2 \leq N \leq 1000) — кількість міст. Кожен із наступних рядків містить цілих чисел. Якщо -те число у -му рядку дорівнює c_{ij}, то видовищність дороги з міста до міста дорівнює 2^{c_{ij}}. Всі c_{ij} — різні та знаходяться у межах від до 10^6 включно. Значення c_{ii} завжди дорівнюють , що означає відсутність дороги з міста у саме себе.
Виведіть послідовність номерів міст, які повинен відвідати граф Гамільтон, щоб його маршрут мав максимальну видовищність. Кожне місто має зустрічатись у цій послідовності рівно один раз, крім початкового міста, яке має зустрічатись двічі — на початку і в кінці. Якщо існує декілька оптимальних маршрутів, виведіть будь-який із них.
Приклад 1