Помогите решить задачу на циклы (или графы, точно не знаю)!!! Послезавтра экзамен!!!

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

решается через принцип дирихле, как один из вариантов. сори но писать дальше лень