using System;

using System.Collections.Generic;

using System.Linq;

​

/* The objective of this exercise is to build a road network connecting every pair of cities.

   Each city should be connected to each other city once.

*/

public class Program

{

    /* Your function RoadBuilder should return a list of new roads required to be built,

    if the existing roads are given by builtRoads and the total number of 

    cities is nCities. Roads should not connect cities to themselves.

    */

    public static int[][] RoadBuilder(int nCities, int[, ] builtRoads)

    {

        //implement the function here

        List<int[]> result = new List<int[]>();

        bool[,] checkRoadExists = new bool[nCities, nCities];

        foreach (int[] city in builtRoads)

        {

            checkRoadExists[city[0],city[1]] = true;

            checkRoadExists[city[1],city[0]] = true;

        }

        for(int i=0; i<nCities;i++)

        {

            for(int j=i+1; j<nCities;j++)

                if(!checkRoadExists[i,j])

                result.Add(new int[]{i,j});

        }

        return result.ToArray();

    }

​

    public static void Main()

    {

        int[, ] test1 = new int[3, 2]{{0, 1}, {1, 2}, {3, 2}};

        Console.WriteLine(RoadBuilder(4, test1)); // expected result should be {{0,2}, {0, 3}, {1, 3}}

    }

}