using System.Collections.Generic;
using System;
using System.Numerics;
using System.Reflection.Emit;
using System.Runtime.Intrinsics;


namespace Lab2
{
    class Graph
    {
        private sbyte[,] IncidenceMatrix { get; set; } = new sbyte[0, 0];
        private string[] VertexesLabels { get; set; } = new string[0];
        private Int64[] EdgesWeights { get; set; } = new Int64[0];
        public IEnumerable<int> VertexIds => Enumerable.Range(0, VertexesLabels.Length);

        public UInt32? First(UInt32 id)
        {
            for (UInt32 i = 0; i < EdgesWeights.Length; i++)
                if (IncidenceMatrix[id, i] == -1)
                    for(UInt32 j = 0; j < VertexesLabels.Length; ++j)
                        if (IncidenceMatrix[j, i] == 1)
                            return j;

            return null;
        }
        public UInt32? Next(UInt32 from, UInt32 id)
        {
            bool takeNext = false;
            for (UInt32 i = 0; i < EdgesWeights.Length; i++)
            {
                if (IncidenceMatrix[from, i] == -1)
                {
                    for (UInt32 j = 0; j < VertexesLabels.Length; ++j)
                    {
                        if (IncidenceMatrix[j, i] != 1)
                            continue;

                        if (takeNext)
                            return j;
                        else if(j == id)
                            takeNext = true;
                    }
                }
            }

            return null;
        }
        public string GetVertex(UInt32 id)
        {
            return VertexesLabels[id];
        }

        public void AddVertex(string label)
        {
            VertexesLabels = VertexesLabels.Append(label).ToArray();
            var newIncidenceMatrix = new sbyte[VertexesLabels.Length, EdgesWeights.Length];
            for (int i = 0; i < IncidenceMatrix.GetLength(0); i++)
                for (int j = 0; j < IncidenceMatrix.GetLength(1); j++)
                    newIncidenceMatrix[i, j] = IncidenceMatrix[i, j];

            IncidenceMatrix = newIncidenceMatrix;
        }
        public void RenameVertex(UInt32 id, string label)
        {
            VertexesLabels[id] = label;
        }
        public void RemoveVertex(UInt32 id)
        {
            throw new NotImplementedException();
        }

        public void AddEdge(UInt32 from, UInt32 to, Int64 weight)
        {
            EdgesWeights = EdgesWeights.Append(weight).ToArray();
            var newIncidenceMatrix = new sbyte[VertexesLabels.Length, EdgesWeights.Length];
            for (int i = 0; i < IncidenceMatrix.GetLength(0); i++)
                for (int j = 0; j < IncidenceMatrix.GetLength(1); j++)
                    newIncidenceMatrix[i, j] = IncidenceMatrix[i, j];

            newIncidenceMatrix[from, EdgesWeights.Length - 1] = -1;
            newIncidenceMatrix[to, EdgesWeights.Length - 1] = 1;
            IncidenceMatrix = newIncidenceMatrix;
        }
        public void SetEdgeWeight(UInt32 from, UInt32 to, Int64 weight)
        {
            for (int i = 0; i < EdgesWeights.Length; i++)
                if (IncidenceMatrix[from, i] == -1 && IncidenceMatrix[to, i] == 1)
                    EdgesWeights[i] = weight;
        }
        public void RemoveEdge(UInt32 from, UInt32 to)
        {
            throw new NotImplementedException();
        }
    };


















    static class WaysSearcher
    {
        public static List<List<UInt32>> SelectPathes(Graph graph, int length)
        {
            List<List<UInt32>> result = new();
            foreach(var id in graph.VertexIds)
            {
                var pathes = SelectPathesRecursive(graph, (UInt32)id, new List<UInt32> {}, length);
                foreach (var path in pathes)
                    result.Add(path);
            }
            return result;
        }
        private static List<List<UInt32>> SelectPathesRecursive(Graph graph, UInt32 currentVertex, List<UInt32> visitedVertexes, int remainedLength)
        {
            var currentPathes = visitedVertexes.ToList().Append(currentVertex).ToList();
            if (remainedLength == 0)
                return new() { currentPathes };

            List<List<UInt32>> result = new();
            for (var id = graph.First(currentVertex); id.HasValue; id = graph.Next(currentVertex, id.Value))
            {
                if (visitedVertexes.Contains(id.Value))
                    continue;

                var pathes = SelectPathesRecursive(graph, id.Value, currentPathes, remainedLength - 1);
                foreach (var path in pathes)
                    result.Add(path);
            }
            return result;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Graph graph = new Graph();
            graph.AddVertex("vertex_1");
            graph.AddVertex("vertex_2");
            graph.AddVertex("vertex_3");
            graph.AddVertex("vertex_4");
            graph.AddEdge(0, 1, 12);
            graph.AddEdge(0, 2, 16);
            graph.AddEdge(1, 3, 12);
            graph.AddEdge(3, 0, 12);
            foreach (var path in WaysSearcher.SelectPathes(graph, 3))
            {
                foreach(var vertex in path)
                    Console.Write($"{vertex} => ");
                Console.WriteLine();
            }
        }
    }
}