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<StartEndAndStringOfCity> cities = new ArrayList<>();

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

        int indexOfCityWithMaximalDepth = 0;
        Vertex<StartEndAndStringOfCity>[] biggestVertexes = g.getMaxSequence(0);
        for (int i = 1; i < strings.length; i++) {
            Vertex<StartEndAndStringOfCity>[] currentVertexes = g.getMaxSequence(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<StartEndAndStringOfCity>[] 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 StartEndAndStringOfCity {
    private static final char[] charsToExcept = {
            'ь'
    };
    private char start;
    private char end;
    private String city;

    /**
     * Получает первый и последний символ по входящему аргументу в параметр city
     *
     * @param city
     */
    StartEndAndStringOfCity(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 canConnectToEnd(StartEndAndStringOfCity string) {
        return (this.end == string.start) ? true : false;
    }

    boolean canConnectToStart(StartEndAndStringOfCity 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 String toString() {
        return "StartEndAndStringOfCity{" +
                "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>[] getMaxSequence(int i) {
        vertexList.get(i).wasVisited = true;
        Stack<T> maximalStack = new Stack<>();
        int maxSequence = 1, currentSequence = 1;
        stack.push(i);
        while (!stack.isEmpty()) {
            int v = getAdjUnvisitedVertex(stack.peek());
            if (v == -1) {
                if (currentSequence > maxSequence) {
                    maxSequence = currentSequence;
                    maximalStack = (Stack<T>) stack.clone();
                }
                currentSequence--;
                stack.pop();
            } else {
                currentSequence++;
                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 GraphForSooqaBlyatPidoraha extends Graph<StartEndAndStringOfCity> {

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

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