using System.Collections.Generic;
using System;

namespace Lab2
{
    class Graph
    {
        public record struct Vertex(UInt32 id, string label);
        public record struct Edge(UInt32 from, UInt32 to, Int64 Weight);

        private UInt32 CurrentVertexMaxId { get; set; } = 0;
        private List<Vertex> Vertices { get; set; } = new();
        private List<Edge> Edges { get; set; } = new();



        public IEnumerable<UInt32> GetVertexesIds() {
            return Vertices.Select(vertex => vertex.id);
        }
        public Vertex GetVertex(UInt32 id) {
            foreach (var vertex in Vertices)
                if(vertex.id == id)
                    return vertex;

            throw new ArgumentOutOfRangeException("Vertex index out of range");
        }
        public UInt32? First(UInt32 id) {
            foreach(var edge in Edges)
                if(edge.from == id)
                    return edge.to;

            return null;
        }
        public UInt32? Next(UInt32 id, UInt32 subvertexId) {
            bool takeNext = false;
            foreach (var edge in Edges)
            {
                if (edge.from != id)
                    continue;

                if(edge.to == subvertexId)
                    takeNext = true;
                else if(takeNext)
                    return edge.to;
            }

            return null;
        }

        public UInt32 AddVertex(string label) {
            var Id = ++CurrentVertexMaxId;
            Vertices.Add(new Vertex(Id, label));
            return Id;
        }
        public void EditVertex(UInt32 id, string label) {
            for (int index = 0; index < Vertices.Count; ++index)
                if (Vertices[index].id == id)
                    Vertices[index] = new Vertex(id, label);//immutable dto
        }
        public void RemoveVertex(UInt32 id) {
            Vertices = Vertices.Where(vertex => vertex.id != id).ToList();
            Edges = Edges.Where(edge => edge.from != id && edge.to != id).ToList();
        }

        public void AddEdge(UInt32 from, UInt32 to, Int64 weight) {
            if (!Edges.Any(edge => edge.from == from && edge.to == to))
                Edges.Add(new Edge(from, to, weight));
        }
        public void EditEdge(UInt32 from, UInt32 to, Int64 weight) {
            for(int index = 0; index < Edges.Count; ++index)
                if (Edges[index].from == from && Edges[index].to == to)
                    Edges[index] = new Edge(from, to, weight);
        }
        public void RemoveEdge(UInt32 from, UInt32 to) {
            Edges = Edges.Where(edge => edge.from == from && edge.to == to).ToList();
        }
    }

    static class WaysSearcher
    {
        public static List<List<UInt32>> SelectPathes(Graph graph, int length)
        {
            List<List<UInt32>> result = new();
            foreach(var id in graph.GetVertexesIds())
            {
                var pathes = SelectPathesRecursive(graph, 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(1, 2, 12);
            graph.AddEdge(1, 3, 16);
            graph.AddEdge(2, 4, 12);
            graph.AddEdge(4, 1, 12);
            foreach (var path in WaysSearcher.SelectPathes(graph, 3))
            {
                foreach(var vertex in path)
                    Console.Write($"{vertex} => ");
                Console.WriteLine();
            }
        }
    }
}