В государстве Радужном некоторые города были соединены друг с ином дорогами,

В государстве Радужном некоторые городка были соединены друг с ином дорогами, но никакой город не был соединён более чем со 125 иными городами. Повелитель решил выкрасить все дороги в 7 цветов радуги (каждую дорогу в один цвет), но его ограничивает древнее предание, сообразно которому молодая дева, выехавшая из собственного городка и возвратившаяся в него, проехав по нечётному количеству дорог, причём все дороги, по которым она проехала, будут 1-го цвета, погубит монархию. Сумеет ли король покрасить дороги так, чтоб не дать шанса юной деве?