Connect the Buildings

The city of Taco is planning to restore connectivity among its futuristic buildings. Each building is located on a 2D plane with given coordinates. A tunnel connecting two buildings costs the Manhattan distance, defined as \( |x_1-x_2|+|y_1-y_2| \). Some tunnels are already operational, and these preexisting tunnels incur no additional cost.

Your task is to compute the minimum additional cost required to ensure that each building is connected either directly or indirectly. This problem can be solved by constructing a Minimum Spanning Tree (MST) of the buildings where each edge weight is the Manhattan distance, while considering the already connected components from the existing tunnels.

inputFormat

The input is read from standard input and is structured as follows:

• The first line contains a single integer \(n\) representing the number of buildings.
• The next \(n\) lines each contain two space-separated integers \(x\) and \(y\) indicating the coordinates of each building.
• The following line contains a single integer \(m\) denoting the number of preexisting tunnels.
• The next \(m\) lines each contain two space-separated integers \(a\) and \(b\) indicating that there is an existing tunnel between the \(a^{th}\) and \(b^{th}\) building (1-indexed).

outputFormat

Output a single integer (to standard output) representing the minimum cost required to connect all buildings.

4
1 1
2 2
3 3
4 4
0

6