Сколько нужно добавить рёбер в этом графе, чтобы из любого города можно было прилететь в любой другой без пересадок?

Сколько нужно добавить рёбер в этом графе,
чтобы из любого города можно было прилететь
в любой другой без пересадок?
Сергей живёт в Санкт-Петербурге и каждый отпуск
навещает бабушку в Екатеринбурге и тётю с дядей, которые живут в Астрахани. Сколько рёбер содержит кратчайший путь?
Если соединить Екатеринбург и Астрахань авиамаршрутом (ребром), сколько рёбер будет содержать кратчайший путь в таком случае?