class Graph
    {
        private List<Node> vertexes;
        private List<Boolean> used = new List<bool>();

        class Node//вершина
        {
            public string name; //хранит название вершины

            //содержит названия вершин, к которым исходят дуги из данной вершины
            public List<string> neighbours = new List<string>();

            //считывание строки
            public Node(string parse)
            {
                char[] separators =
                {
                    ':',
                    ','
                };

                string[] parseResult = parse.Split(separators);
                name = parseResult[0];
                for (int i = 1; i < parseResult.Length; i++)
                {
                    neighbours.Add(parseResult[i]);
                }

            }

            // выводит название вершины
            public void print()
            {
                if (neighbours.Count == 0)
                {
                    Console.WriteLine("- Вершина " + name + " не имеет исходящих дуг.");
                    return;
                }

                Console.WriteLine("-Вершина " + name + ":");
                Console.WriteLine("Исходящие дуги:");
                foreach (var i in neighbours)
                {
                    Console.WriteLine("" + name + "-> " + i + "");
                }
            }

            /** добавляет в список вершин-"соседей"
             * вершину с заданным именем
             */
            public void addEdge(string newEdge)
            {
                neighbours.Add(newEdge);
            }

            /** удаляет из списка вершин-"соседей"
             * все вхождения deletedEdge
             */
            public void deleteEdge(string deletedEdge)
            {
                while (neighbours.Remove(deletedEdge)) ;
            }

            public void deleteEdge(int deletedEdge)
            {
                for (int i = 0; i < neighbours.Count; i++)
                {
                    if (int.Parse(neighbours[i]) == deletedEdge)
                    {
                        neighbours.RemoveAt(i);
                    }
                }
            }
        }


        public Graph()
        {
            vertexes = new List<Node>(); //пустой список вершин
        }


        public Graph(string filename)
        {
            vertexes = new List<Node>();
            StreamReader fileReader = new StreamReader(filename);
            string stringBuff;
            while ((stringBuff = fileReader.ReadLine()) != null)
            {
                addNode(stringBuff);
                used.Add(false);
            }
        }

        public Graph(Graph source)
        {
            vertexes = new List<Node>();
            foreach (Node i in source.vertexes)
            {
                vertexes.Add(i);
            }
        }

        /** Публичный конструктор Graph(int) создает полный граф с числами-названиями вершин по умолчанию. */
        public Graph(int num)
        {
            vertexes = new List<Node>();
            string buff;
            for (int i = 0; i < num; i++)
            {
                buff = Convert.ToString(i) + ":";
                for (int j = 0; j < num; j++)
                {
                    if (j != i)
                    {
                        buff += Convert.ToString(j);
                    }
                }
                addNode(buff);
            }
        }

        /** добавляет в список вершин новую
         * принимая строку из файла
         */
        public void addNode(string parse)
        {
            vertexes.Add(new Node(parse));
        }

        /** удаляет из списка вершин
         * вершину с заданным именем nodeName, а также все
         * её упоминания в списках вершин"соседей" остальных вершин.
         */
        public void deleteNode(string nodeName)
        {
            for (var i = 0; i < vertexes.Count; i++)
            {
                if (nodeName == vertexes[i].name)
                {
                    vertexes.Remove(vertexes[i]);
                }
                else
                {
                    vertexes[i].deleteEdge(nodeName);
                }
            }
        }

        public void deleteNode(int x)
        {
            for (var i = 0; i < vertexes.Count; i++)
            {
                if (x == int.Parse(vertexes[i].name))
                {
                    vertexes.Remove(vertexes[i]);
                }
                else
                {
                    vertexes[i].deleteEdge(x);
                }
            }
        }

        /**добавляет в число вершин-"соседей"
         * вершины sourceNode вершину destinationNode, т.е. создаёт дугу из вершины sourceNode
         * в вершину destinationNode.
         */
        public void addEdge(string sourceNode, string destinationNode)
        {
            try
            {
                vertexes.Find(element => element.name == sourceNode).addEdge(destinationNode);
            }
            catch (Exception)
            {
                Console.WriteLine("Такой исходящей/адресуемой вершины не существует");
            }
        }

        /** удаляет все имеющиеся в графе
         * дуги с началом в вершине sourceNode и концом в вершине destinationNode.
         */
        public void deleteEdge(string sourceNode, string destinationNode)
        {
            vertexes.Find(element => element.name == sourceNode).deleteEdge(destinationNode);
        }

        //выводит информацию обо всех вершинах
        public void infoAboutGraph()
        {
            foreach (var i in vertexes)
            {
                i.print();
            }
            Console.WriteLine();
        }

        public void findDisconnectedNodes(string key)
        {
            var disnodes = vertexes.Where(x => x.name != key && !x.neighbours.Contains(key)).Select(x => x.name).ToArray();
            Console.Write("Disconnected nodes: ");
            foreach (var i in disnodes)
            {
                Console.Write(i + " ");
            }
            Console.WriteLine();
        }

        public void newGraphByDeleteEdges()
        {
            List<int> result = new List<int>();
            for(int i = 0; i < vertexes.Count; i++)
            {
                //ищем нечётную вершину в орграфе
                var res = vertexes.Where(x => x.neighbours.Contains((i+1).ToString())).Count()+vertexes[i].neighbours.Count;
                result.Add(res);
            }

            for (int i = 0; i < result.Count; i++)
            {
                if(result[i]%2!=0)
                    vertexes[i].deleteEdge(vertexes[i].neighbours[0]);
            }
            infoAboutGraph();
        }

        public void dfs(string key)
        {
            used[int.Parse(key) - 1] = true;
            Console.Write(key+ " ");
            for (int i = 0; i < vertexes[int.Parse(key) - 1].neighbours.Count; i++)
            {
                if (!used[int.Parse(vertexes[int.Parse(key) - 1].neighbours[i]) - 1])
                {
                    dfs(vertexes[int.Parse(key) - 1].neighbours[i]);
                }
            }
        }

        public void findRoot()
        {
            for (int i = 0; i < vertexes.Count; i++)
            {
                Console.WriteLine();
                dfs((i + 1).ToString());
                if (used.All(x => x == true))
                {
                    Console.WriteLine(i + 1 + "root");
                    for (int j = 0; j < used.Count; j++)
                    {
                        used[j] = false;
                    }

                }
                else
                    Console.WriteLine(i + 1 + "isn't root");
            }
        }
    }
/*****************INPUT FILE***********************
1:2,4
2:1,3
3:2,4
4:1,3,5
5:4
*********************************************/