На День учителя благодарные ученики подарили Егору Сергеевичу несколько железнодорожных билетов, чтобы он совершил путешествие по России.

Билеты были для проезда между следующими парами городов:

Санкт-Петербург и Тверь,
Ярославль и Нижний Новгород,
Москва и Санкт-Петербург,
Нижний Новгород и Казань,
Москва и Казань,
Москва и Нижний Новгород.

Билеты были с открытой датой: по каждому билету можно проехать один раз в любую сторону между городами.

Егор Сергеевич в итоге смог побывать ровно по одному разу в шести городах. В каком городе могло начаться путешествие? Укажите все возможные варианты.

• Казань
• Москва
• Нижний Новгород
• Санкт-Петербург
• Тверь
• Ярославль