Для того чтобы решить задачу о том, какое наименьшее число дорог нужно добавить, чтобы из городов выходило поровну дорог, нам нужно учесть несколько моментов.

Шаг 1: Определение текущего состояния

• Сначала нам нужно выяснить, сколько дорог (или рёбер) выходит из каждого города (или вершины). Это можно сделать, составив список всех городов и подсчитав количество дорог, которые к ним ведут.

Шаг 2: Анализ четности

• Каждая дорога соединяет два города и добавляет по одной дороге к каждому из них. Это означает, что если у города нечётное количество дорог, то он не будет удовлетворять условию "поровну".
• Таким образом, мы должны определить, сколько городов имеют нечётное количество дорог. Это можно сделать, пройдя по списку и подсчитав количество городов с нечётным числом рёбер.

Шаг 3: Применение теоремы о четных и нечётных вершинах

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

Шаг 4: Подсчёт необходимых добавлений

• Если количество городов с нечётным числом дорог чётное, то для того чтобы сделать их степени чётными, нам нужно добавить половину от этого количества дорог. Например, если у нас 4 города с нечётным количеством дорог, то нам нужно добавить 4/2 = 2 дороги.
• Если количество городов с нечётным числом дорог нечётное, то мы не можем сделать все степени чётными, и задача не имеет решения в рамках данной модели.

Таким образом, подводя итог, мы можем сказать, что для решения задачи нужно:

1. Подсчитать количество городов с нечётным числом дорог.
2. Если это количество чётное, то разделить его на 2, чтобы узнать, сколько дорог нужно добавить.
3. Если это количество нечётное, то решение невозможно.