Subtask 1

A key observation is that at least ~N - 1~ pipes are needed to connect all buildings. In addition, the location of the water pump does not matter. For the first subtask, all pipes can be moved to a different location, thus the answer is ~\max(0, N - 1 - M)~. You don't even need to read the full input!

Time Complexity: ~\mathcal{O}(1)~

Subtask 2

For the second subtask, a key observation is that the number of additional pipes is equal to ~C - 1~ where ~C~ is the number of connected components in the graph. This can be computed in a number of ways, including breadth first search, depth first search, of the union find data structure.

Time Complexity: ~\mathcal{O}(N + M)~ or ~\mathcal{O}(N + M \cdot \alpha(N))~

Subtask 3

For the third subtask, a key observation is that if a connected component has ~V~ vertices, then only ~V - 1~ edges are required to keep it connected. All other edges should be moved. Specifically, these edges should be moved to connect two connected components. These edges can be computed in a similar manner to subtask 2. Let ~L~ be the number of such edges that can be moved and ~C~ be the number of connected components. Recall that ~C - 1~ edges are required to connect all the connected components. Thus, the answer is equal to ~\max(0, C - 1 - \min(K, L))~.

Time Complexity: ~\mathcal{O}(N + M)~ or ~\mathcal{O}(N + M \cdot \alpha(N))~