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

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

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

Варианты ответов:

Казань

Москва

Нижний Новгород

Сакт-Петербург

Тверь

Ярославль