В стране несколько городов, некоторые соединены дорогами. Известно, что из каждого города дорог выходит на 6 меньше, чем всего городов в стране. Также известно, что число дорог, выходящих из каждого города, является простым.

Самая длиная линия из дорог A1, A2,___  Ak,

каждые два соседних города в этой последовательности соединены дорогой.

Если из городов A1 и Ak выходит ровно одна дорога .

Тогда пусть, например, из A1 идет дорога в  город B, . Если B – один из городов A3, ___, Ak, то возникает цикл из дорог, что противоречит условию. Таким образом, город B отличвется от городов A1, A2, ___, Ak. Получается что в последовательности городов B, A1, A2,  Ak города по парам размечены  .

Соседние города соединены дорогой. Но эта последовательность содержит больше k городов не смотря на то что  выбору последовательности A1, A2, Ak.