class Graphe {

    int nb ;            // Nombre de sommets
    Liste[] listeSucc ; // Listes d'adjacence
    String[] mot ;
    boolean[] dejaVu ; // Pour le parcours en profondeur.
    int[] pere ;

    Graphe (String[] lesMots) { // Construit un graphe sans ar^etes
	nb = lesMots.length ;
	mot = lesMots ;
	listeSucc = new Liste [nb] ;
	for (int i=0 ; i<nb ; ++i)
	    listeSucc [i] = null ; // Pas de voisin pour l'instant
	dejaVu = new boolean [nb] ;
	pere = new int [nb] ;
    }

    static void afficher (Graphe g) {
	for (int i=0 ; i<g.nb ; ++i) {
	    System.out.print (g.mot [i] + " -> ") ;
	    for (Liste v=g.listeSucc [i] ; v!=null ; v=v.suivant)
		System.out.print (g.mot [v.contenu] + " ") ;
	    System.out.println () ;
	}
    }
  
    static void lettreQuiSaute (Graphe g) {
	for (int i=0 ; i<g.nb ; ++i)
	    for (int j=i+1 ; j<g.nb ; ++j)
		if (diffUneLettre (g.mot[i], g.mot[j]))
		    ajouterArete (g, i, j) ;
    }

    static void ajouterArete (Graphe g, int s, int d) { // graphe symmetrique
	g.listeSucc [s] = new Liste (d, g.listeSucc [s]) ;
	g.listeSucc [d] = new Liste (s, g.listeSucc [d]) ;
    }

    static boolean diffUneLettre (String a, String b) { 
	// a et b supposes de meme longueur
	int i=0 ;
	while (i<a.length () && a.charAt (i) == b.charAt (i)) 
	    ++i ;
	if (i == a.length ())
	    return false ;
	++i ;
	while (i<a.length () && a.charAt (i) == b.charAt (i)) 
	    ++i ;
	return i == a.length () ;
    }


    static void dfs (Graphe g, int x) {
	g.dejaVu[x] = true ;
	//System.out.print (g.mot[x] + " ") ;
	for (Liste ls = g.listeSucc[x] ; ls != null ; ls = ls.suivant) {
	    int y = ls.contenu ;
	    if (!g.dejaVu[y]) {
		g.pere[y] = x ;
		dfs(g, y) ;
	    }
	}
    }

    static void visit (Graphe g) {
	initVisit (g) ;
	int num_comp = 1 ;
	for (int x = 0 ; x < g.nb ; ++x)
	    if (! g.dejaVu[x]) {
		System.out.print (num_comp + ":   ") ;
		num_comp++ ;
		//dfs (g, x);
		dfsIteratif (g, x) ;
		//bfsIteratif (g, x);
		System.out.println () ;
	    }
    }

    static void initVisit (Graphe g) {
	for (int x = 0 ; x < g.nb ; ++x) {
	    g.dejaVu[x] = false ;
	    g.pere[x] = -1 ;
	}
    }
    
    static void chemin (Graphe g, String from, String to){
	int f = indice (from, g.mot) ;
	int t = indice (to, g.mot) ;
	initVisit (g) ;
	bfsIteratif (g, t) ;
	//dfs (g, t) ;
	if (! g.dejaVu[f])
	    System.out.print ("Pas de chemin de " + from + " a " + to + " !") ;
	else
	    while (f != -1) {
		System.out.print (g.mot[f] + " ") ;
		f = g.pere[f] ;
	    }
	System.out.println () ;
    }

    static int indice (String m, String[] tabMots) {
	for (int i=0 ; i<tabMots.length ; ++i)
	    if (m.equals (tabMots[i])) return i ;
	throw new Error (m + " n'est pas dans le tableau.") ;
    }

    static void dfsIteratif (Graphe g, int x) {
	Pile aVisiter = new Pile (x) ;
	g.dejaVu [x] = true ;
	while (Pile.nonVide (aVisiter)) {
	    int i = Pile.depiler (aVisiter) ;
	    System.out.print (g.mot[i] + " ") ;
	    for (Liste ls = g.listeSucc[i] ; ls != null ; ls = ls.suivant) {
		int y = ls.contenu ;
		if (! g.dejaVu [y]) {
		    g.dejaVu [y] = true ;
		    Pile.empiler (aVisiter, y) ;
		    g.pere[y] = i ;
		}
	    }
	}
    }

    static void bfsIteratif (Graphe g, int x) {
	FIFO aVisiter = new FIFO (x) ;
	g.dejaVu [x] = true ;
	while (FIFO.nonVide (aVisiter)) {
	    int i = FIFO.supprimer (aVisiter) ;
	    //System.out.print (g.mot[i] + " ") ;
	    for (Liste ls = g.listeSucc[i] ; ls != null ; ls = ls.suivant) {
		int y = ls.contenu ;
		if (! g.dejaVu [y]) {
		    g.dejaVu [y] = true ;
		    FIFO.ajouter (aVisiter, y) ;
		    g.pere[y] = i ;
		}
	    }
	}
    }
    
    public static void main (String[] args) {
	String[] dico3court = { "gag", "gai", "gaz", "gel", "gks", "gin", "gnu", "glu", "gui", "guy", "gre", "gue", "ace", "acm", "agi", "ait", "aie", "ail", "air", "and", "alu", "ami", "arc", "are", "art", "apr", "avr", "sur", "mat", "mur" } ;
	//Graphe g = new Graphe (dico3court) ;
	Graphe g = new Graphe (Dicos.dico4) ;
	lettreQuiSaute (g) ;
	//afficher (g) ;
	visit (g) ;
	System.out.println () ;
	chemin (g, args[0], args[1]) ;
    }
}