50178. Longest Cycle

I'm a slow walker, but I never walk backwards.

Task Description

There are N cities indexed from 0 to N - 1, and a set of bidirection roads connecting these cities. You will be given an adjacency matrix $A$ to represent these roads. That is, if $A_{i, j}$ is 1, then there is a road between city i and j. Otherwise it is 0 and there is no road between the cities.

Now we start from city 0, and we want to find the longest cycle that goes through cities without visiting any city twice, and finally get back to city 0. If the longest cycle is 0 → A → B → C → 0, then the output will be A B C in a line where A, B, and C are indices of cities. If there are multiple longest cycles, output the first one in dictionary order. For example, 1 2 4 appears earlier than 1 3 2 in the dictionary order. We assume that there will be a cycle including city 0 of length no less than three.

Input Format

The first line contains an integer N which represents the number of cities. Then there are N x N integers for the adjacency matrix.

  • $3 ≤ N ≤ 8$

Output Format

If the longest cycle is 0 → A → B → C → 0, then output A B C in a line. If there are multiple longest cycles, output the first one in dictionary order.

Sample Input 1

6
0 1 0 0 1 0
1 0 1 0 1 0
0 1 0 1 0 0
0 0 1 0 1 1
1 1 0 1 0 0
0 0 0 1 0 0

Sample Output 1

1 2 3 4

Sample Input 2

4
0 0 1 1
0 0 0 1
1 0 0 1
1 1 1 0

Sample Output 2

2 3

Sample Input 3

7
0 0 0 1 1 0 1
0 0 1 0 0 0 1
0 1 0 1 1 0 1
1 0 1 0 1 0 0
1 0 1 1 0 0 0
0 0 0 0 0 0 1
1 1 1 0 0 1 0

Sample Output 3

3 4 2 1 6

Discussion