using System.Collections.Generic;
using System;
using System.Numerics;
using System.Reflection.Emit;
using System.Runtime.Intrinsics;
using static Lab2.Graph;

namespace Lab2
{
    class Graph
    {
        public class Edge
        {
            public Int64 Weight { get; set; }
            public UInt32 From { get; }
            public UInt32 To { get; }
            public Edge(UInt32 from, UInt32 to, Int64 weight)
            {
                Weight = weight;
                From = from;
                To = to;
            }
	    }
        public class Vertex
        {
            public UInt32 Id { get; }
            public string Label { get; set; }
            public SortedDictionary<UInt32, Edge> Edges { get; } = new();

            public Vertex(UInt32 id, string label)
            {
                Id = id;
                Label = label;
            }

            void addEdge(UInt32 to, Int64 weight)
            {
                Edges.TryAdd(to, new Edge(Id, to, weight));
            }
            void removeEdge(UInt32 to)
            {
                Edges.Remove(to);
            }
        }

        private SortedDictionary<UInt32, Vertex> Vertexes { get; } = new();
        public List<UInt32> VertexIds => Vertexes.Keys.ToList();
        private UInt32 GlobalVertexId { get; set; } = 0;

        public UInt32? First(UInt32 id)
        {
            if (Vertexes.ContainsKey(id))
                if (Vertexes[id].Edges.Count > 0)
                    return Vertexes[id].Edges.Keys.First();

            return null;
        }
        public UInt32? Next(UInt32 from, UInt32 id)
        {
            if ((Vertexes.ContainsKey(id) && Vertexes.ContainsKey(from)) == false)
                return null;

            var nextVertexesIds = Vertexes[from].Edges.Keys.ToList();
            for(int index = 0; index < nextVertexesIds.Count; ++index)
                if (nextVertexesIds[index] == id)
                    if(index != nextVertexesIds.Count - 1)
                        return nextVertexesIds[index + 1];

            return null;
        }
        public Vertex? GetVertex(UInt32 id)
        {
            return Vertexes.GetValueOrDefault(id);
        }

        public void AddVertex(string label)
        {
            var id = ++GlobalVertexId;
            Vertexes.Add(id, new Vertex(id, label));
        }
        public void RenameVertex(UInt32 id, string label)
        {
            var vertex = Vertexes.GetValueOrDefault(id);
            if (vertex is not null)
                vertex.Label = label;
        }
        public void RemoveVertex(UInt32 id)
        {
            Vertexes.Remove(id);
            foreach(var vertex in Vertexes)
                vertex.Value.Edges.Remove(id);
        }

        public void AddEdge(UInt32 from, UInt32 to, Int64 weight)
        {
            if(Vertexes.ContainsKey(from) && Vertexes.ContainsKey(to))
                Vertexes[from].Edges.TryAdd(to, new Edge(from, to, weight));
        }
        public void SetEdgeWeight(UInt32 from, UInt32 to, Int64 weight)
        {
            if (Vertexes.ContainsKey(from) && Vertexes.ContainsKey(to))
                if(Vertexes[from].Edges.ContainsKey(to))
                    Vertexes[from].Edges[to] = new Edge(from, to, weight);
        }
        public void RemoveEdge(UInt32 from, UInt32 to)
        {
            if (Vertexes.ContainsKey(from) && Vertexes.ContainsKey(to))
                Vertexes[from].Edges.Remove(to);
        }
    };


















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, 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();
            }
        }
    }
}