Let's rephrase this problem in terms of graph theory. We are required to generate a connected graph with ~N~ nodes and ~M~ bidirectional unweighted edges, such that sum of distances between all pairs of nodes is minimised.

Subtask 1

In this subtask, the graph is a tree. We can show that the optimal tree is a star graph, in which one node is connected to every other node. This is because there must be exactly ~N-1~ pairs of nodes which are a distance of ~1~ apart in any construction, and for the remaining pairs of nodes, the star graph guarantees that they are a distance of ~2~ apart.

Time complexity: ~\mathcal{O}(M)~

Subtask 2

Again, there must be exactly ~M~ pairs of nodes which are a distance of ~1~ apart, so any construction which guarantees that all remaining pairs of nodes are a distance of ~2~ apart will be optimal. This can be achieved by starting with a star graph, and repeatedly adding edges until there are ~M~ edges in total.

Time complexity: ~\mathcal{O}(M)~