#комбинаторика #задача

В стране n городов и n дорожных компаний. Между некоторыми парами городов проложены дороги, каждая принадлежит какой-то из компаний. Между двумя городами может быть проложено больше одной дороги. Каждая компания владеет нечётным числом дорог, причём эти дороги образуют замкнутый маршрут. Докажите, что найдётся замкнутый маршрут нечётной длины, все дороги которого принадлежат разным компаниям.