22-2 # 6

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


public class Graph
{

    public string[] f;

    private class Node //вложенный класс для скрытия данных и алгоритмов
    {
        public void Show()
        {
            for (int i = 0; i < array.GetLength(0); ++i)
            {
                for (int j = 0; j < array.GetLength(0); ++j)
                    Console.Write(array[i, j] + " ");
                Console.WriteLine();
            }
        }
        public void ExcludeNode(int k)
        {
            for (int i = 0; i < array.GetLength(0); ++i)
                array[i, k] = array[k, i] = 0;

        }
       public static int[] p;

       public void Solve(int a, int b)
       {
          a--;b--;
          BFS(a);
          if (p[b] == -1)
            {
              Console.WriteLine("No path");
              return;
            }
          int i = b;
          List<int> path = new List<int>();
          while (p[i] != i)
          {
            path.Add(i);
            i = p[i];
          }
          path.Add(i);
          path.Reverse();
          Console.WriteLine($"path from {a + 1} to {b + 1}");
          foreach( var v in path)
            Console.Write(v + 1 + " ");
          Console.WriteLine();
       }
       int sz;
       public void BFS(int sourse)
        {
            for(int i = 0; i < sz; ++i)
              p[i] = -1;
            Queue<int> q = new Queue<int>();
            q.Enqueue(sourse);
            p[sourse] = sourse;
            while (q.Count != 0)
            {

              int v = q.Dequeue();
              //Console.Write(v + " ");
              for (int i = 0; i < sz; ++i)
              {
                if (array[v, i] != 0 && p[i] == -1)
                  {
                    q.Enqueue(i);
                    p[i] = v;
                  }
              }

            }
        }
        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;
            sz = a.GetLength(0);
            nov = new bool[sz];
            p = new int[sz];
        }




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

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


            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]);
                }
            }
            graph = new Node(a);
        }
    }
    //метод выводит матрицу смежности на консольное окно
    public void Show()
    {
        graph.Show();
    }



    public void ExcludeNode(int k)
    {
        graph.ExcludeNode(k);
    }


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

        Graph gr = new Graph("input.txt");
        gr.Solve(1, 5);
       /*
       5
0 1 0 1 0
0 0 1 1 0
0 0 0 0 1
0 1 0 1 0
1 1 0 0 0
*/

    }

}