In Graph City, there are buildings, numbered from to . Water is currently distributed through a system of pipes, with pipe allowing water to flow in both directions between buildings and . Unfortunately, water can only flow into a building if there are a series of pipes that form a path connecting it to the water pump, located at building . Due to poor city planning, the current arrangement of pipes may not allow all buildings to receive water. The city has hired you to help them solve this problem!
Thankfully, the city has recruited enough volunteers to help you move some of the existing pipes to new locations for free, however they are only willing to do this at most times. Additional pipes can be built at any location at the cost of . The city wants to know the minimum cost required to allow water to flow to all of the buildings.
For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.
For all subtasks:
There will be at most one pipe directly connecting any two buildings.
The first line contains 3 integers, , , and .
The next lines describe the current arrangement of pipes in the city. Each line contains 2 integers, , , indicating a pipe allowing water to flow in both directions between buildings to .
This problem is graded with an
identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a
\n character and that there are no trailing spaces.
Output a single integer, the minimum cost required to build new pipes to allow water to flow into all buildings, after moving at most of the existing pipes.
Sample Input 1
4 6 6 1 2 3 4 4 2 3 1 4 1 3 2
Sample Output 1
Sample Explanation 1
Since all buildings are connected to the water pump, no new pipes are built or moved.
Sample Input 2
4 1 0 2 3
Sample Output 2
Sample Explanation 2
We can build a pipe between buildings and , and another pipe between buildings and to connect all buildings to the water pump, for a total cost of . The built pipes are coloured in green.
Sample Input 3
6 4 1 1 2 2 3 3 1 4 5
Sample Output 3
Sample Explanation 3
We can move the existing pipe between buildings and (red) to connect buildings and (blue) for free. We can then build a new pipe between buildings and (green), which costs .