22- III

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

public class Stack
{
    private class Node //вложенный класс, реализующий элемент стека
    {
        private object inf;
        private Node next;
        public Node(object nodeInfo)
        {
            inf = nodeInfo;
            next = null;
        }
        public Node Next
        {
            get { return next; }
            set { next = value; }
        }
        public object Inf
        {
            get { return inf; }
            set { inf = value; }
        }
    } //конец класса Node
    private Node head; //ссылка на вершину стека
    public Stack() //конструктор класса, создает пустой стек
    {
        head = null;
    }
    public void Push(object nodeInfo) // добавляет элемент в вершину стека
    {
        Node r = new Node(nodeInfo);
        r.Next = head;
        head = r;
    }
    public object Pop() //извлекает элемент из вершины стека, если он не пуст
    {
        if (head == null)
        {
            throw new Exception("Стек пуст");
        }
        else
        {
            Node r = head;
            head = r.Next;
            return r.Inf;
        }
    }
    public bool IsEmpty //определяет пуст или нет стек
    {
        get
        {
            if (head == null)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }
}

public class Graph
{

    public string[] f;

    private class Node //вложенный класс для скрытия данных и алгоритмов
    {
        private int[,] array; //матрица смежности
        public int this[int i, int j] //индексатор для обращения к матрице смежности
        {
            get
            {
                return array[i, j];
            }
            set
            {
                array[i, j] = value;
            }
        }
        public bool this[int i] //индексатор для обращения к матрице меток
        {
            get
            {
                return nov[i];
            }
            set
            {
                nov[i] = value;
            }
        }
        public int Size //свойство для получения размерности матрицы смежности
        {
            get
            {
                return array.GetLength(0);
            }
        }
        private bool[] nov; //вспомогательный массив: если i-ый элемент массива равен
                            //true, то i-ая вершина еще не просмотрена; если i-ый
                            //элемент равен false, то i-ая вершина просмотрена
        public void NovSet() //метод помечает все вершины графа как непросмотреные
        {
            for (int i = 0; i < Size; i++)
            {
                nov[i] = true;
            }
        }
        //конструктор вложенного класса, инициализирует матрицу смежности и
        // вспомогательный массив
        public Node(int[,] a)
        {
            array = a;
            nov = new bool[a.GetLength(0)];
        }
        //реализация алгоритма обхода графа в глубину
        public void Dfs(int v)
        {
            Console.Write("{0} ", v); //просматриваем текущую вершину
            nov[v] = false; //помечаем ее как просмотренную
                            // в матрице смежности просматриваем строку с номером v
            for (int u = 0; u < Size; u++)
            {
                //если вершины v и u смежные, к тому же вершина u не просмотрена,
                if (array[v, u] != 0 && nov[u])
                {
                    Dfs(u); // то рекурсивно просматриваем вершину
                }
            }
        }
        //реализация алгоритма обхода графа в ширину
        public void Bfs(int v)
        {
            Queue<int> q = new Queue<int>();
            q.Enqueue(v); //помещаем вершину v в очередь
            nov[v] = false; // помечаем вершину v как просмотренную
            while (q.Count != 0) // пока очередь не пуста
            {
                v = Convert.ToInt32(q.Dequeue()); //извлекаем вершину из очереди
                Console.Write("{0} ", v); //просматриваем ее
                for (int u = 0; u < Size; u++) //находим все вершины
                {
                    if (array[v, u] != 0 && nov[u]) // смежные с данной и еще не просмотренные
                    {
                        q.Enqueue(u); //помещаем их в очередь
                        nov[u] = false; //и помечаем как просмотренные
                    }
                }
            }
        }

        public long[] Dijkstr(int v, out int[] p)
        {
            nov[v] = false; // помечаем вершину v как просмотренную
                            //создаем матрицу с
            int[,] c = new int[Size, Size];
            for (int i = 0; i < Size; i++)
            {
                for (int u = 0; u < Size; u++)
                {
                    if (array[i, u] == 0 || i == u)
                    {
                        c[i, u] = int.MaxValue;
                    }
                    else
                    {
                        c[i, u] = array[i, u];
                    }
                }
            }
            //создаем матрицы d и p
            long[] d = new long[Size];
            p = new int[Size];
            for (int u = 0; u < Size; u++)
            {
                if (u != v)
                {
                    d[u] = c[v, u];
                    p[u] = v;
                }
            }
            for (int i = 0; i < Size - 1; i++) // на каждом шаге цикла
            {
                // выбираем из множества V\S такую вершину w, что D[w] минимально
                long min = int.MaxValue;
                int w = 0;
                for (int u = 0; u < Size; u++)
                {
                    if (nov[u] && min > d[u])
                    {
                        min = d[u];
                        w = u;
                    }
                }
                nov[w] = false; //помещаем w в множество S
                                //для каждой вершины из множества V\S определяем кратчайший путь от
                                // источника до этой вершины
                for (int u = 0; u < Size; u++)
                {
                    long distance = d[w] + c[w, u];
                    if (nov[u] && d[u] > distance)
                    {
                        d[u] = distance;
                        p[u] = w;
                    }
                }
            }
            return d; //в качестве результата возвращаем массив кратчайших путей для
        }




        public void SearchGm(int k, ref int[] St, ref bool fl)
        {
            int v = St[k - 1];
            if (!fl)
                return;
            for (int j = 0; j < array.GetLength(0); j++)
            {
                if (array[v, j] != 0)
                {
                    if (k == array.GetLength(0))
                    {
                        St[k] = j;
                        foreach (int item in St)
                        {
                            Console.Write("{0} ", item + 1);
                        }
                        Console.WriteLine();
                        fl = false;
                        return;

                    }
                    else
                    {
                        if (nov[j])
                        {
                            St[k] = j;
                            nov[j] = false;
                            SearchGm(k + 1, ref St, ref fl);
                            nov[j] = true;
                        }
                    }

                }

            }

        }

    } //конец вложенного клаcса
    private Node graph; //закрытое поле, реализующее АТД «граф»


    public Graph(string name) //конструктор внешнего класса
    {
        using (StreamReader file = new StreamReader($"D:/{name}"))
        {
            int n = int.Parse(file.ReadLine());
            int[,] a = new int[n, n];
            f = file.ReadLine().Split(' ');

            for (int i = 0; i < n; i++)
            {
                string line = file.ReadLine();
                string[] mas = line.Split(' ');
                for (int j = 0; j < n; j++)
                {
                    a[i, j] = int.Parse(mas[j]);
                    if (a[i, j] == 0)
                        a[i, j] = int.MaxValue;
                }
            }
            graph = new Node(a);
        }
    }
    //метод выводит матрицу смежности на консольное окно
    public void Show()
    {
        for (int i = 0; i < graph.Size; ++i)
            Console.Write("\t" + f[i]);
        Console.WriteLine("\n");
        for (int i = 0; i < graph.Size; i++)
        {
            Console.Write(f[i] + "\t");
            for (int j = 0; j < graph.Size; j++)
            {
                if (graph[i, j] == int.MaxValue)
                    Console.Write("INF\t");
                else
                    Console.Write(graph[i,j] + "\t");
            }
            Console.WriteLine("\n");
        }
    }
    public void Dfs(int v)
    {
        graph.NovSet();
        graph.Dfs(v);
        Console.WriteLine();
    }
    public void Bfs(int v)
    {
        graph.NovSet();
        graph.Bfs(v);
        Console.WriteLine();
    }

    public long[] Dijkstr(int v)
    {
        graph.NovSet();
        int[] p;
        long[] d = graph.Dijkstr(v, out p);
        return d;
    }


    public void Solve(int n)
    {

        bool[,]used = new bool[graph.Size, graph.Size];
        for (int i = 0; i < graph.Size; ++i)
            for (int j = 0; j < graph.Size; ++j)
                if (graph[i, j] != int.MaxValue && !used[i,j] && !used[j,i])
                {
                    used[i, j] = true;

                    int was = graph[i, j];
                    graph[i, j] = graph[j, i] = int.MaxValue;

                    bool fl = true;
                    for (int k = 0; k < graph.Size; k++)
                    {
                        long[] dist = Dijkstr(k);
                        Array.Sort(dist);
                        if (dist[dist.Length - 1] > n)
                        {
                            break;
                            fl = false;
                        }
                    }
                    graph[i, j] = graph[j, i] = was;
                    if (fl == true)
                    {
                        Console.WriteLine($"YES : we can delete way from {f[i]} to {f[j]}");
                        return;
                    }

                }
            Console.WriteLine("NO");
    }

    public void SearchGm(int start)//внешний класс Гамильтонов
    {
        graph.NovSet();
        int[] St = new int[graph.Size + 1];
        St[0] = 0;
        graph[0] = false; //обращение к индексатору
        //int start = int.Parse(Console.ReadLine());
        bool fl = true;
        graph.SearchGm(start, ref St, ref fl);
    }

    public int GetLength()
    {
        return graph.Size;
    }
}
class Program
{
    static void Main(string[] args)
    {

        Graph gr = new Graph("input.txt");
        gr.Show();
        gr.Solve(100);
        /*
         * 5
a b c d f
0 70 0 0 20
70 0 75 25 15
0 75 0 40 60
0 25 40 0 0
20 15 60 0 0
         */
    }

}