using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

class HamiltonianCycleFinder
{
    private readonly int[,] graph; 
    private readonly int n;
    private volatile List<int>? result = null;

    public HamiltonianCycleFinder(int[,] graph)
    {
        this.graph = graph;
        this.n = graph.GetLength(0);
    }

    public List<int>? FindHamiltonianCycle(int startVertex)
    {
        var path = new List<int> { startVertex };
        var visited = new bool[n];
        visited[startVertex] = true;

        FindCycleParallel(startVertex, path, visited);
        return result;
    }

    private void FindCycleParallel(int currentVertex, List<int> path, bool[] visited)
    {
        if (result != null) return;


        if (path.Count == n)
        {
            if (graph[currentVertex, path[0]] == 1)
            {
                lock (this)
                {
                    if (result == null)
                    {
                        result = new List<int>(path) { path[0] };
                    }
                }
            }
            return;
        }

        Parallel.For(0, n, i =>
        {
            if (graph[currentVertex, i] == 1 && !visited[i] && result == null)
            {
                var newVisited = new bool[visited.Length];
                Array.Copy(visited, newVisited, visited.Length);
                newVisited[i] = true;
                var newPath = new List<int>(path) { i };
                FindCycleParallel(i, newPath, newVisited);
            }
        });
    }

    static void Main(string[] args)
    {
        //int[,] graph = {
        //    { 0, 1, 1, 0 },
        //    { 1, 0, 1, 1 },
        //    { 1, 1, 0, 1 },
        //    { 0, 1, 1, 0 }
        //};
        int[,] graph = {
            { 0, 0, 0, 0 },
            { 0, 0, 1, 1 },
            { 0, 1, 0, 1 },
            { 0, 1, 1, 0 }
        };

        var finder = new HamiltonianCycleFinder(graph);
        int startVertex = 0;

        var cycle = finder.FindHamiltonianCycle(startVertex);

        if (cycle != null)
        {
            Console.WriteLine("Hamiltonian Cycle found:");
            Console.WriteLine(string.Join(" -> ", cycle));
        }
        else
        {
            Console.WriteLine("No Hamiltonian Cycle exists.");
        }
    }
}