import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        String[] strings = {
                "Москва",
                "Саратов",
                "Свердловск",
                "Астана",
                "Астрахань",
                "Санкт-петербург",
                "Гурьев",
                "Начало",
                "Орёл",
                "Липецк",
                "Кишенёв",
                "Владимир",
                "Ростов",
                "Воронеж",
                "Житомир",
                "Минск",
                "Киров",
                "Норильск",
                "Муром",
                "Донецк",
                "Тьмутаракань",
                "Омск",
                "Каракум",
                "Волгоград",
                "Уфа",
                "Тарту",
                "Рига",
                "Юрмола"
        };
//        Vertex v = new Vertex();
        final int N = strings.length;
        boolean ll[][] = new boolean[N][N];

        List<SEOfString> cities = new ArrayList<>();

        for (String city :
                strings) {
            cities.add(new SEOfString(city));
        }
        GraphSEOfString g = new GraphSEOfString(N);
        for (SEOfString city :
                cities) {
            g.addVertex(city);
        }

        int indexOfCityWithMaximalDepth = 0;
        Vertex<SEOfString>[] biggestVertexes = g.dfs(0);
        for (int i = 1; i < strings.length; i++) {
            Vertex<SEOfString>[] currentVertexes = g.dfs(i);
            if (biggestVertexes.length < currentVertexes.length) {
                indexOfCityWithMaximalDepth = i;
                biggestVertexes = currentVertexes;
            }
        }

        System.out.println("Самая большая последовательность у города \"" + strings[indexOfCityWithMaximalDepth] + "\"" + " c " + biggestVertexes.length + " городами");
        displayCHEEKYBREEKY(biggestVertexes);
    }
    public static void displayCHEEKYBREEKY(Vertex<SEOfString>[] toDisplay){
        System.out.print("[Размер последовательности равен " +toDisplay.length  + "] "+toDisplay[0].label.getCity());
        for (int i = 1; i < toDisplay.length; i++) {
            System.out.print(" \u2192 " + toDisplay[i].label.getCity());
        }
        System.out.println("\n");
    }
}

/**
 * Start and end chars of string
 */
class SEOfString {
    private static final char[] charsToExcept = {
            'ь'
    };
    private char start;
    private char end;
    private String city;

    /**
     * Получает первый и последний символ по входящему аргументу в параметр city
     *
     * @param city
     */
    SEOfString(String city) {
        start = Character.toLowerCase(city.charAt(0));
        int lastIndex = city.length() - 1;
        while (isExceptionChar(city.charAt(lastIndex))) {
            lastIndex--;
        }
        end = city.charAt(lastIndex);
        this.city = city;
    }

    boolean connectEnd(SEOfString string) {
        return (this.end == string.start) ? true : false;
    }

    boolean connectStart(SEOfString string) {
        return (this.start == string.end) ? true : false;
    }

    /**
     * @param symbol
     * @return
     */
    private boolean isExceptionChar(char symbol) {
        for (char illegalChar :
                charsToExcept) {
            if (symbol == illegalChar) {
                return true;
            }
        }
        return false;
    }

    public char getEnd() {
        return end;
    }

    public char getStart() {
        return start;
    }

    public String getCity() {
        return city;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        SEOfString that = (SEOfString) o;

        if (start != that.start) return false;
        if (end != that.end) return false;
        return city.equals(that.city);

    }

    @Override
    public int hashCode() {
        int result = (int) start;
        result = 31 * result + (int) end;
        result = 31 * result + city.hashCode();
        return result;
    }

    @Override
    public String toString() {
        return "SEOfString{" +
                "start=" + start +
                ", end=" + end +
                ", city='" + city + '\'' +
                '}';
    }
}

class Vertex<T> {
    public T label;
    public boolean wasVisited;

    public Vertex(T label) {
        wasVisited = false;
        this.label = label;
    }

    @Override
    public String toString() {
        return "Vertex{" +
                "label=" + label +
                ", wasVisited=" + wasVisited +
                '}';
    }
}

class Graph<T> {
    protected final ArrayList<Vertex<T>> vertexList;
    protected final boolean[][] adjMat;
    protected final Stack<Integer> stack;

    public Graph(int N) {
        vertexList = new ArrayList<>();
        adjMat = new boolean[N][N];
        stack = new Stack<>();
    }

    public void addVertex(T vertex) {
        vertexList.add(new Vertex<T>(vertex));
    }

    public void addEdge(int start, int end) {
        adjMat[start][end] = true;
    }

    public void displayVertex(int v) {
        System.out.println(vertexList.get(v));
    }

    public Vertex<T>[] dfs(int i) {
        vertexList.get(i).wasVisited = true;
        Stack<T> maximalStack = new Stack<>();
        int maxNOfCities = 1, currentNOfCities = 1;
        stack.push(i);
        while (!stack.isEmpty()) {
            int v = getAdjUnvisitedVertex(stack.peek());
            if (v == -1) {
                if (currentNOfCities > maxNOfCities) {
                    maxNOfCities = currentNOfCities;
                    maximalStack = (Stack<T>) stack.clone();
                }
                currentNOfCities--;
                stack.pop();
            } else {
                currentNOfCities++;
                vertexList.get(v).wasVisited = true;
                stack.push(v);
            }
        }
        for (Vertex v : vertexList) {
            v.wasVisited = false;
        }
        Vertex<T>[] maxD = new Vertex[maximalStack.size()];
        while (!maximalStack.isEmpty()) {
            maxD[maximalStack.size() - 1] = vertexList.get((Integer) maximalStack.peek());
            maximalStack.pop();
        }
        return maxD;
    }

    protected int getAdjUnvisitedVertex(int peek) {
        for (int i = 0; i < vertexList.size(); i++) {
            if (adjMat[peek][i] && !vertexList.get(i).wasVisited) {
                return i;
            }
        }
        return -1;
    }
}

class GraphSEOfString extends Graph<SEOfString> {

    public GraphSEOfString(int N) {
        super(N);
    }

    @Override
    public void addVertex(SEOfString newCity) {
        super.addVertex(newCity);
        for (int i = 0; i < vertexList.size() - 1; i++) {
            SEOfString string = vertexList.get(i).label;
            if (newCity.connectEnd(string)) {
                adjMat[vertexList.size() - 1][i] = true;
            } else if (newCity.connectStart(string)) {
                adjMat[i][vertexList.size() - 1] = true;
            }
        }
    }
}