Minimum router Peripherality Breadth First Search (BFS) Algorithm performance

Question

I have solved the MinRouterPeripherality task in codility using javascript using Breadth First Search(BFS) approach.

However time complexity is O(N^2). I am really struggling to make performance improvement necessary so I can get the time complexity to possibly O(N) or close to it

Task: https://app.codility.com/programmers/task/min_router_peripherality/ Solved Report: https://app.codility.com/demo/results/trainingQ87TKA-9R2/

I am not 100% sure what improvements I could do to achieve this in Javascript.

    // you can write to stdout for debugging purposes, e.g.
    // console.log('this is a debug message');

    function solution(T) {
    // console.log(T);

    const treeMap = {}
    if(T.length < 3) {
          let min = Math.min(...T);

          return T.indexOf(min);
    }

    T.forEach((q, i)=>{
        if (q === i) {
            return;
        }

        if(!treeMap[q]) {
            treeMap[q] = [];
        }

        if(!treeMap[i]) {
            treeMap[i] = [];
        }

        treeMap[q].push(i);
        treeMap[i].push(q)
    });


    // Calculate distances
    const calcs = (n) => {
        let distanceMap = {};
        let queue = [n];
        let visited = [];
        let distance = 0;
        masterMap[n][n] = 0;
        const calculateDistances = (p) => {
            let start = p;
            visited.push(p)
    //        masterMap[n][p] = 0;
            let children = treeMap[p];

            if(!distanceMap[p]){
                distanceMap[p] = 0;
            }

            children.forEach((c) => {
                if(visited.indexOf(c) > -1) {
                    return;
                }

                distanceMap[c] = distanceMap[p] + 1;
             //   distance += distanceMap[c];

                if(!masterMap[c]) {
                    masterMap[c] = []
                }
                masterMap[n][c] = distanceMap[c];
                masterMap[c][n] = distanceMap[c];
             //   runs++;
            //    console.log('====', c, p, n)
            //    console.log(masterMap)
            //    console.log('====')
                queue.push(c)
            });

        };

        for(let i = 0; i < routerNodes.length; i++ ) {
            calculateDistances(queue.shift());
        }

      //  console.log(distanceMap)

        return distance;    
    }

    const routerNodes = Object.keys(treeMap);

    let pdCalculations = [];
    let masterMap = [];
   // let runs = 0;
    for(let i = 0; i < routerNodes.length; i++ ) {
        if(masterMap[i] && Object.keys(masterMap[i]).length === (routerNodes.length - 1)) {
          break;   
        }
        if(!masterMap[i]) {
            masterMap[i] = [];
            masterMap[i][i] = 0
        }
       // console.log(masterMap[i])
        calcs(i);   
    }

   for(let k = 0; k < masterMap.length; k++ ) {
         pdCalculations.push(masterMap[k].reduce((a, b)=> a + b, 0))
   }

  // let value = Object.keys(pdCalculations).sort((a, b) => pdCalculations[a] - pdCalculations[b])[0];
   let min = Math.min.apply(null, pdCalculations);
  // console.log(min);

    return pdCalculations.indexOf(min);
  // return parseInt(value);

}