Question

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