Как мы найдём начальный город маршрута?

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

Важно различать эти постановки: при потерянном направлении есть два равноправных конца. В корректной простой цепочке ровно две вершины степени 1, остальные — степени 2. Цикл, ветвление или разрыв требуют другой обработки и не соответствуют такому условию.