using System;

using System.Collections.Generic;

using System.Linq;

​

public class Program

{

    public static void Main()

    {

    }

    public static List<List<int>> find_critical_connections(int number_of_servers, List<List<int>> connections) 

    {

        // find a node which is connected only one neighbour, essentially in-degree & out-degree is 1

        var result = new List<List<int>>();

        var adjList = BuildGraph(number_of_servers, connections);

        TraverseBFS(0, adjList, result);

        if(result.Count == 0) result.Add(new List<int>(){-1, -1});

        return result;

    }

    static void TraverseBFS(int start, List<List<int>> adjList, List<List<int>> result)

    {

        bool[] visited = new bool[adjList.Count];

        int[] parent = new int[adjList.Count];

        Queue<int> queue = new Queue<int>();

        queue.Enqueue(start);

        visited[start] = true;

        parent[start] = -1;

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

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

        while(queue.Count > 0)

        {

            var node = queue.Dequeue();

            foreach(var ngb in adjList[node])

            {

                if(!visited[ngb])

                {

                    visited[ngb] = true;

                    parent[ngb] = node;

                    if(adjList[ngb].Count == 1)

                    {

                        result.Add(new List<int>(){node, ngb});

                        edgeFrom.Add(node);

                        edgeTo.Add(ngb);

                    }

                    queue.Enqueue(ngb);

                }

                // if the neighbour are 1

                if(adjList[ngb].Count == 1)

                {

                    if(!edgeFrom.Contains(node) && !edgeTo.Contains(ngb))

                    {

                        result.Add(new List<int>(){node, ngb});

                        edgeFrom.Add(node);

                        edgeTo.Add(ngb);

                    }

                }

            }

        }

    }

    static List<List<int>> BuildGraph(int number_of_servers, List<List<int>> connections)

    {

        List<List<int>> adjList = new List<List<int>>();

        for(int i = 0; i < number_of_servers; i++) adjList.Add(new List<int>());

        foreach(var edge in connections)

        {

            adjList[edge[0]].Add(edge[1]);

            adjList[edge[1]].Add(edge[0]);

        }

        return adjList;

    }

​

}

​

​