def is_valid(v, graph, path, pos):
    # Check if the current vertex v can be added to the path
    if graph[path[pos-1]][v] == 0:
        return False
    # Check if the vertex has already been visited
    if v in path:
        return False
    return True

def hamiltonian_util(graph, path, pos):
    # Base case: If all vertices are included in the path
    if pos == len(graph):
        # Check if there is an edge from the last included vertex to the first vertex
        if graph[path[pos-1]][path[0]] == 1:
            return True
        else:
            return False
    for v in range(1, len(graph)):
        if is_valid(v, graph, path, pos):
            path[pos] = v
            if hamiltonian_util(graph, path, pos+1):
                return True
            # Backtrack and try other vertices
            path[pos] = -1
    return False

def hamiltonian_circuit(graph):
    n = len(graph)
    path = [-1] * n
    # Start from the first vertex (0)
    path[0] = 0
    if not hamiltonian_util(graph, path, 1):
        print("No Hamiltonian circuit exists")
        return False
    print("Hamiltonian circuit:")
    for vertex in path:
        print(vertex, end=" ")
    print(path[0])  # Print the first vertex again to complete the circuit
    return True