/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
        Ideone u = new Ideone();
	}
	
	public Map<String, Vertex> miestai = new HashMap<>();
    public List<List<Vertex>> marsrutai = new ArrayList<>();

    public Ideone() {
        // sudedam miestus
        miestai.put("Kaunas", new Vertex("Kaunas"));
        miestai.put("Vilnius", new Vertex("Vilnius"));
        miestai.put("Karmelava", new Vertex("Karmelava"));
        miestai.put("Klaipeda", new Vertex("Klaipeda"));
        miestai.put("Siauliai", new Vertex("Siauliai"));
        miestai.put("Panevezys", new Vertex("Panevezys"));
        // sudedam marsrutus
        miestai.get("Kaunas").addMarsrutas(miestai.get("Vilnius"));
        miestai.get("Kaunas").addMarsrutas(miestai.get("Siauliai"));
        miestai.get("Kaunas").addMarsrutas(miestai.get("Klaipeda"));
        miestai.get("Vilnius").addMarsrutas(miestai.get("Kaunas"));
        miestai.get("Vilnius").addMarsrutas(miestai.get("Karmelava"));
        miestai.get("Karmelava").addMarsrutas(miestai.get("Kaunas"));
        miestai.get("Karmelava").addMarsrutas(miestai.get("Klaipeda"));
        miestai.get("Klaipeda").addMarsrutas(miestai.get("Vilnius"));
        miestai.get("Klaipeda").addMarsrutas(miestai.get("Siauliai"));
        miestai.get("Siauliai").addMarsrutas(miestai.get("Panevezys"));

        // paieska
        getMarsrutai("Vilnius", "Panevezys");

        // tikrinam rezultatus
        for (int i = 0; i < marsrutai.size(); i++) {
            for (int j = 0; j < marsrutai.get(i).size(); j++) {
                System.out.print(marsrutai.get(i).get(j).vardas + " ");
            }
            System.out.println();
        }
    }

    // paieska
    public void getMarsrutai(String fromName, String toName) {
        Vertex from = miestai.get(fromName);
        Vertex to = miestai.get(toName);

        Stack<Vertex> visited = new Stack<>();
        visited.add(from);

        Queue<Vertex> toVisit = new LinkedList<>(from.marsrutai); // pasiekiami miestai is esamo miesto
        while (toVisit.peek() != null) {
            getMarsrutai(toVisit.poll(), to, visited);
        }
    }

    /**
     * Rekursija
     * @param from Dabartine stotis
     * @param to Tikslas
     * @param visited Aplankytos stoteles
     */
    public void getMarsrutai(Vertex from, Vertex to, Stack<Vertex> visited) {
        if (from.equals(to)) { // pasiekeme tiksla
            visited.add(from);
            marsrutai.add(new ArrayList<>(visited));
            visited.pop();
            return;
        }

        if (visited.contains(from)) { // apsauga nuo begalinio ciklo
            return;
        }

        visited.add(from); // idedamam esama vieta i aplankytu sarasa
        Queue<Vertex> toVisit = new LinkedList<>(from.marsrutai); // pasiekiami miestai is esamo miesto
        while (toVisit.peek() != null) {
            getMarsrutai(toVisit.poll(), to, visited);
        }

        visited.pop(); // isimam, kad vel galetume pasiekti si miesta
    }

    class Vertex {
        String vardas;
        List<Vertex> marsrutai = new ArrayList<>();

        public Vertex(String vardas) {
            this.vardas = vardas;
        }

        public void addMarsrutas(Vertex m) {
            marsrutai.add(m);
        }
    }
}