Hamiltonian cycle#1680
Count William Hamilton decided to embark on a journey to visit the largest cities on Earth. There are roads connecting every pair of cities. Each road has a spectacularity value, which is a power of . The spectacularity of a road can differ depending on the direction of travel, and all road spectacularity values are distinct. The Count wants 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.
The first line contains (2 \leq N \leq 1000) — the number of cities.
Each of the following lines contains integers. If the -th number in the -th line is c_{ij}, then the spectacularity of the road from city to city is 2^{c_{ij}}. All c_{ij} are distinct and range from to 10^6, inclusive. The values c_{ii} are always , which means that there is no road from a city to itself.
Output the sequence of city numbers that Count Hamilton should visit so that his route achieves the maximum spectacularity. Each city must appear exactly once in this sequence, except for the starting city, which appears twice — at the beginning and at the end. If there are several optimal routes, output any of them.
Example 1