Hamiltonian cycle in a complete graph
Given a graph with N vertices, where each vertex has a degree of at least N/2, your task is to find a Hamiltonian cycle.
Input
The input begins with an integer N (3 ≤ N ≤ 4000), representing the number of vertices in the graph. Following this, there are N lines that describe the adjacency matrix of the graph. The matrix is symmetric, and the diagonal entries are always zero. The i-th line contains i-1 symbols, which are either zeros or ones. A one at the j-th position in the i-th line indicates the presence of an edge between vertices i and j.
It is guaranteed that the graph contains a Hamiltonian cycle and that each vertex has a degree of at least N/2.
Output
Output a permutation of N numbers, representing the vertices in the order they appear in the Hamiltonian cycle.