Проблема с поиском Гамильтонова цикла

В задании требуется найти гамильтонов цикл, который начинается с вершины, введённой пользователем. Если цикл построить нельзя, необходимо вывести -1. Даётся неориентированный граф с n вершинами. Cам граф задаётся матрицей смежности.

Реализация графа:

class Graph{

private:
    int num;
    vector<int> path;
    vector<bool> visited;

public:
    explicit Graph(int value){
        num = value;
        visited.resize(num, false);
    }

    void print(){
        for (int i = 0; i < path.size(); i++){
            cout << path[i] << ' ';
        }
    }

    void fill(vector<vector<int>>& matrix){
        for (int i = 0; i < matrix.size(); i ++){
            for (int j = 0; j < matrix.size(); j ++){
                cin >> matrix[i][j];
            }
        }
    }

Реализация построения цикла:

bool HamiltonCycle(vector<vector<int>>& matrix, int start) {
        path.push_back(start);
        if (path.size() == matrix.size()){
            if (matrix[path[0]][path.back()] == 1){
                return true;
            }
            else{
                path.pop_back();
                return false;
            }
        }
        visited[start - 1] = true;
        for (int i = 0; i < matrix.size(); ++i){
            if (matrix[start - 1][i] == 1 and !visited[i]){
                if (HamiltonCycle(matrix, i + 1)){
                    return true;
                }
            }
        }
        visited[start - 1] = false;
        path.pop_back();
        return false;
    }

Проблема: При пустом графе или дереве, программа ведет себя отлично

(прим: Для данных вида: Программа выдает правильный цикл: 4 5 3 1 2 4).

5 4

0 1 1 0 0

1 0 0 1 0

1 0 0 1 1

0 1 1 0 1

0 0 1 1 0

Но для подобного графа, начинаются проблемы и программа выдаёт цикл вида: 1 5 2 6 4 3 1 Cам граф и его матрица смежности:

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

Пробежался дебагером про коду, но так ничего не нашёл.