using System;

using System.Collections.Generic;   

​

public class Program

{

    public static void Main()

    {

        int[] result = FindRedundantConnection(new int[,] { {1,2}, {2,3}, {3,4}, {1,4}, {1,5} });

        Console.WriteLine(result[0] + ":" + result[1]);

    }

    public static int[] FindRedundantConnection(int[,] edges)

    {

        Dictionary<int, List<int>> pairs = new Dictionary<int, List<int>>();

        HashSet<int> hs = new HashSet<int>();

        for(int i = 0; i < edges.GetLength(0); i++)

        {

            if(pairs.ContainsKey(edges[i,0]) && pairs.ContainsKey(edges[i, 1]) && dfs(pairs, edges[i,0], edges[i,1], hs))

            {

                return new int[] { edges[i, 0], edges[i, 1] };

            }

            if(!pairs.ContainsKey(edges[i,0]))

            {

                pairs.Add(edges[i,0], new List<int>());

            }

            if(!pairs.ContainsKey(edges[i,1]))

            {

                pairs.Add(edges[i,1], new List<int>());

            }

            pairs[edges[i, 0]].Add(edges[i, 1]);

            pairs[edges[i, 1]].Add(edges[i, 0]);

        }

        return new int[] { -1, -1 };

    }

    public static bool dfs(Dictionary<int, List<int>> pairs, int e1, int e2, HashSet<int> hs)

    {

        if(!hs.Contains(e1))

        {

            hs.Add(e1);

            if(e1 == e2) return true;

            List<int> n = pairs[e1];

            for(int i = 0; i < n.Count; i++)

            {

                if(dfs(pairs, n[i], e2, hs))

                {

                    return true;

                }

            }

        }

        return false;

    }

}