В стране 110 городов, между каждыми двумя из них есть дорога, либо её нет. Какое наибольшее значение может принимать N?

В стране 110 городов. Между каждыми двумя из них либо есть дорога, либо её нет.
Автомобилист находился в некотором городе, из которого вела ровно одна дорога. Проехав по дороге, он оказался во втором городе, из которого вели уже ровно две дороги. Проехав по одной из них, он оказался в третьем городе, из которого вели уже ровно три дороги, и так далее. В какой-то момент, проехав по одной из дорог, он оказался в N-м городе, из которого вели уже ровно N дорог. На этом автомобилист своё путешествие прекратил. (Для каждого 2 ⩽ k ⩽ N из k-го города выходило ровно k дорог с учётом той, по которой автомобилист в этот город приехал.) Какое наибольшее значение может принимать N?