Во владении короля имеется

городов, которые не соединены дорогами. Король захотел построить дороги между некоторыми парами городов так, что если два города не связаны новой дорогой, то из одного города в другой можно добраться по крайней мере двумя разными маршрутами по новым дорогам, дополнительно проезжая ровно через один город. Какое наименьшее количество дорог может быть построено?
Вот такая задача! Пожалуйста, подскажите, направьте на путь решения :)