import java.util.Collection;
import java.util.LinkedHashSet;

public class Main {
        static String[] cities = new String[] {
                "абакан",
                "азов",
                "александров",
                "алексин",
                "альметьевск",
                "анапа",
                "ангарск",
                "анжеро-судженск",
                "апатиты",
                "арзамас",
                "армавир",
                "арсеньев",
                "артем",
                "архангельск",
                "асбест",
                "астрахань",
                "ачинск",
                "балаково",
                "балахна",
                "балашиха",
                "балашов",
                "барнаул",
                "батайск",
                "белгород",
                "белебей",
                "белово",
                "белогорск",
                "белорецк",
                "белореченск",
                "бердск",
                "березники",
                "березовский",
                "бийск",
                "биробиджан",
                "благовещенск",
                "бор",
                "борисоглебск",
                "боровичи",
                "братск",
                "брянск",
                "бугульма",
                "буденновск",
                "бузулук",
                "буйнакск",
                "великие луки",
                "великий новгород",
                "верхняя пышма",
                "видное",
                "владивосток",
                "владикавказ",
                "владимир",
                "волгоград",
                "волгодонск",
                "волжск",
                "волжский",
                "вологда",
                "вольск",
                "воркута",
                "воронеж",
                "воскресенск",
                "воткинск",
                "всеволожск",
                "выборг",
                "выкса",
                "вязьма",
                "гатчина",
                "геленджик",
                "георгиевск",
                "глазов",
                "горно-алтайск",
                "грозный",
                "губкин",
                "гудермес",
                "гуково",
                "гусь-хрустальный",
                "дербент",
                "дзержинск",
                "димитровград",
                "дмитров",
                "долгопрудный",
                "домодедово",
                "донской",
                "дубна",
                "евпатория",
                "егорьевск",
                "ейск",
                "екатеринбург",
                "елабуга",
                "елец",
                "ессентуки",
                "железногорск",
                "железногорск",
                "жигулевск",
                "жуковский",
                "заречный",
                "зеленогорск",
                "зеленодольск",
                "златоуст",
                "иваново",
                "ивантеевка",
                "ижевск",
                "избербаш",
                "иркутск",
                "искитим",
                "ишим",
                "ишимбай",
                "йошкар-ола",
                "казань",
                "калининград",
                "калуга",
                "каменск-уральский",
                "каменск-шахтинский",
                "камышин",
                "канск",
                "каспийск",
                "кемерово",
                "керчь",
                "кинешма",
                "кириши",
                "киров",
                "кирово-чепецк",
                "киселевск",
                "кисловодск",
                "клин",
                "клинцы",
                "ковров",
                "когалым",
                "коломна",
                "комсомольск-на-амуре",
                "копейск",
                "королев",
                "кострома",
                "котлас",
                "красногорск",
                "краснодар",
                "краснокаменск",
                "краснокамск",
                "краснотурьинск",
                "красноярск",
                "кропоткин",
                "крымск",
                "кстово",
                "кузнецк",
                "кумертау",
                "кунгур",
                "курган",
                "курск",
                "кызыл",
                "лабинск",
                "лениногорск",
                "ленинск-кузнецкий",
                "лесосибирск",
                "липецк",
                "лиски",
                "лобня",
                "лысьва",
                "лыткарино",
                "люберцы",
                "магадан",
                "магнитогорск",
                "майкоп",
                "махачкала",
                "междуреченск",
                "мелеуз",
                "миасс",
                "минеральные воды",
                "минусинск",
                "михайловка",
                "михайловск",
                "мичуринск",
                "москва",
                "мурманск",
                "муром",
                "мытищи",
                "набережные челны",
                "назарово",
                "назрань",
                "нальчик",
                "наро-фоминск",
                "находка",
                "невинномысск",
                "нерюнгри",
                "нефтекамск",
                "нефтеюганск",
                "нижневартовск",
                "нижнекамск",
                "нижний новгород",
                "нижний тагил",
                "новоалтайск",
                "новокузнецк",
                "новокуйбышевск",
                "новомосковск",
                "новороссийск",
                "новосибирск",
                "новотроицк",
                "новоуральск",
                "новочебоксарск",
                "новочеркасск",
                "новошахтинск",
                "новый уренгой",
                "ногинск",
                "норильск",
                "ноябрьск",
                "нягань",
                "обнинск",
                "одинцово",
                "озерск",
                "октябрьский",
                "омск",
                "орел",
                "оренбург",
                "орехово-зуево",
                "орск",
                "павлово",
                "павловский посад",
                "пенза",
                "первоуральск",
                "пермь",
                "петрозаводск",
                "петропавловск-камчатский",
                "подольск",
                "полевской",
                "прокопьевск",
                "прохладный",
                "псков",
                "пушкино",
                "пятигорск",
                "раменское",
                "ревда",
                "реутов",
                "ржев",
                "рославль",
                "россошь",
                "ростов-на-дону",
                "рубцовск",
                "рыбинск",
                "рязань",
                "салават",
                "сальск",
                "самара",
                "санкт-петербург",
                "саранск",
                "сарапул",
                "саратов",
                "саров",
                "свободный",
                "севастополь",
                "северодвинск",
                "северск",
                "сергиев посад",
                "серов",
                "серпухов",
                "сертолово",
                "сибай",
                "симферополь",
                "славянск-на-кубани",
                "смоленск",
                "соликамск",
                "солнечногорск",
                "сосновый бор",
                "сочи",
                "ставрополь",
                "старый оскол",
                "стерлитамак",
                "ступино",
                "сургут",
                "сызрань",
                "сыктывкар",
                "таганрог",
                "тамбов",
                "тверь",
                "тимашевск",
                "тихвин",
                "тихорецк",
                "тобольск",
                "тольятти",
                "томск",
                "троицк",
                "туапсе",
                "туймазы",
                "тула",
                "тюмень",
                "узловая",
                "улан-удэ",
                "ульяновск",
                "урус-мартан",
                "усолье-сибирское",
                "уссурийск",
                "усть-илимск",
                "уфа",
                "ухта",
                "феодосия",
                "фрязино",
                "хабаровск",
                "ханты-мансийск",
                "хасавюрт",
                "химки",
                "чайковский",
                "чапаевск",
                "чебоксары",
                "челябинск",
                "черемхово",
                "череповец",
                "черкесск",
                "черногорск",
                "чехов",
                "чистополь",
                "чита",
                "шадринск",
                "шали",
                "шахты",
                "шуя",
                "щекино",
                "щелково",
                "электросталь",
                "элиста",
                "энгельс",
                "южно-сахалинск",
                "юрга",
                "якутск",
                "ялта",
                "ярославль",
        };

    Collection<String> bestQueueCities = new LinkedHashSet<>();

    public static void main(String[]args) {
        new Main();
    }

    public Main() {
            for (String city : cities) {
                    Collection<String> strings = new LinkedHashSet<>();
                    strings.add(city);
                    unidirectionGraph(strings, city);
            }
            System.out.println(bestQueueCities);
    }

    public void unidirectionGraph(Collection<String> queueCities, String lastedCity) {
            char lastChar = lastedCity.charAt(lastedCity.length() - 1);
            for (String city : cities) {
                    if(!queueCities.contains(city) &&
                            city.charAt(0) == lastChar) {
                            Collection<String> newQueueCities = new LinkedHashSet<>(queueCities);

                            newQueueCities.add(city);
                            unidirectionGraph(new LinkedHashSet(newQueueCities), city);
                    }
            }
            if(bestQueueCities.size() < queueCities.size()) {
                    bestQueueCities = queueCities;
                    System.out.println(bestQueueCities.size() + " ||| " + bestQueueCities);
            }
    }
}