Try every pair of different cities and calculate its network rank.

The network rank of two vertices is <i>almost</i> the sum of their degrees.

How can you efficiently check if there is a road connecting two different cities?