Hamiltonian cycle
Once upon a time, Count William Hamilton decided to embark on a journey around the world, visiting the N largest cities on Earth. There are roads connecting every pair of cities. Each road has a spectacularity value, which is a power of 2. The spectacularity of a road differs depending on the direction of travel, and all roads have unique spectacularity values. The Count aims to select a closed route that starts and ends in the same city, visits each city exactly once, and maximizes the total spectacularity.
Write a program to determine the optimal closed route for Count Hamilton.
Input
The first line contains an integer N - the number of cities (2 ≤ N ≤ 1000). Each of the following N lines contains N numbers. If the j-th number in the i-th line is c_ij, then the spectacularity of the road from city i to city j is 2^cij. All numbers c_ij are distinct and range from 0 to 10^6 inclusive. The values c_ii are always -1, indicating that roads from a city to itself do not exist.
Output
Output the sequence of city numbers that Count Hamilton should visit to achieve the maximum spectacularity for his route. Each city should appear exactly once in this sequence, except for the starting city, which should appear twice - at the beginning and at the end. If there are multiple optimal routes, any of them can be output.