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

class Graphe {

    int nb ;            // Nombre de sommets
    Liste[] listeSucc ; // Listes d'adjacence
    String[] mot ;
    Hashtable index ; // un_mot -> son indexe dans mot
    Hashtable prefixe ; // prefixe d'un_mot -> existe ou pas
    boolean[] dejaVu ; // Pour le parcours en profondeur.
    int[] pere ;
    int[] distance ; // distance au premier sommet visite dans un bfs

    Graphe (String[] lesMots) { // Construit un graphe sans ar^etes
	init (this, lesMots) ;
    }

    static void init (Graphe g, String[] lesMots) { // Construit un graphe sans ar^etes
	g.nb = lesMots.length ;
	g.mot = lesMots ;
	g.index = new Hashtable (g.nb) ;
	g.prefixe = new Hashtable (g.nb) ;
	g.listeSucc = new Liste [g.nb] ;
	for (int i=0 ; i<g.nb ; ++i) {
	    g.index.put (g.mot[i], new Integer (i)) ;
	    StringBuffer s = new StringBuffer () ;
	    // On identifie tous les prefixes de mots
	    Boolean present = new Boolean (true) ;
	    for (int c=0 ; c<g.mot[i].length () ; ++c) {
		s.append (g.mot[i].charAt (c)) ;
		g.prefixe.put (s.toString (), present) ;
	    }
	    g.listeSucc [i] = null ; // Pas de successeur pour l'instant
	}
	g.dejaVu = new boolean [g.nb] ;
	g.pere = new int [g.nb] ;
	g.distance = new int [g.nb] ;
    }

    Graphe (File f) { // Lit les mots depuis un fichier
	java.util.Vector vecMots = new java.util.Vector () ;
	try {
	    BufferedReader in = new BufferedReader (new FileReader (f)) ;
	    while (true) {
		String s = in.readLine () ;
		if (s == null) break ;
		s.trim  () ;
		vecMots.addElement (s) ;
	    }
	} catch (Exception e) { System.out.println (e) ; }
	String[] lesMots = new String [vecMots.size ()] ;
	for (int i=0 ; i<vecMots.size () ; ++i)
	    lesMots[i] = (String) vecMots.elementAt (i) ;
	init (this, lesMots) ;
    }


    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, int sup, int dif) { 
        for (int i=0 ; i<g.nb ; ++i) 
            testSuccesseurs (g, i, 0, new StringBuffer (), sup, dif) ; 
    } 
 
    // teste tous les mots possible obtenus a partir de a
    //   en suprimant au plus sup lettres et en changeant
    //   au plus dif lettres, ceux qui sont des mots du
    //   dictionnaire sont ajoutes a la liste des successeurs
    //   de i
    // 6min17 sans test sur les prefixes
    // 4min17 avec test
    // Rq : ce serait plus efficace en espace memoire avec un trie
    static void testSuccesseurs (Graphe g, int i, int posa, 
				 StringBuffer b, int sup, int dif) { 
	String a = g.mot[i] ;
        int la = a.length () ;

	// Plus de modification possible, b contient un successeur possible
        if (posa >= la) { 
            Integer j = (Integer) g.index.get (b.toString ()) ;
	    if (j != null && !Liste.membre (g.listeSucc[i], j.intValue())) 
		// b correspond bien a un mot du dictionnaire
		// non encore identifie comme successeur de i
		ajouterArete (g, i, j.intValue()) ;
	    return ;
        }

	if (sup > 0)
	    // On supprime la lettre
	    testSuccesseurs (g, i, posa+1, b, sup-1, dif) ;

	int posb = b.length () ;
	b.append ('a') ;

	if (dif > 0) {
	    // On change la lettre
	    for (char c='a' ; c<='z' ; ++c) {
		b.setCharAt (posb, c) ;
		if (g.prefixe.containsKey (b.toString ()))
		    // si ce n'est pas un prefixe possible,
		    //   inutile d'essayer
		    testSuccesseurs (g, i, posa+1, b, sup, dif-1) ;
	    }
		
	}

	// On laisse la lettre telle quelle
	b.setCharAt (posb, a.charAt (posa)) ;
	testSuccesseurs (g, i, posa+1, b, sup, dif) ;

	// On remet b en etat
	b.setLength (posb) ;
    } 
 
    // Trop lent, O(n^2)  21min14 sur tout.dicofrancais
    static void lettreQuiSauteLent (Graphe g, int sup, int dif) {
	for (int i=0 ; i<g.nb ; ++i)
	    for (int j=0 ; j<g.nb ; ++j)
		if (diffPlusieursLettres (g.mot[i], 0, g.mot[j], 0, sup, dif))
		    ajouterArete (g, i, j) ;
    }

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

    static boolean diffPlusieursLettres (String a, int posa, String b, int posb, int sup, int dif) { 
	// peut-on passer de a[posa;findea] a b[posb;findeb] en supprimant au plus sup lettres de a et en changeant au plus dif

	int la = a.length (), lb = b.length () ;
	if (lb - posb > la - posa || lb - posb < la - posa - sup) 
	    return false ;

	// S'il y a moyen de transformer a en b
        // alors il y a moyen de le faire en gardant le plus long
        //   prefixe de a qui est aussi un prefixe de b
	while (posb<lb && a.charAt (posa) == b.charAt (posb)) { 
	    ++posa ; ++posb ;
	}
	if (posb == lb)
	    return true ;

	// On essaye de changer la lettre si possible
	if (dif > 0 && diffPlusieursLettres (a, posa+1, b, posb+1, sup, dif-1))
	    return true ;

	// On essaye de supprimer la lettre de a
	if (sup > 0 && diffPlusieursLettres (a, posa+1, b, posb, sup-1, dif)) 
            return true ; 

	return false ;    
    }


    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 ;
	    g.distance[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, f) ;
	//dfs (g, t) ;
	if (! g.dejaVu[t])
	    System.out.print ("Pas de chemin de " + from + " a " + to + " !") ;
	else
	    printChemin (g, t) ;
	System.out.println () ;
    }

    static void printChemin (Graphe g, int to) {
	if (to != -1) {
	    printChemin (g, g.pere [to]) ;
	    System.out.print (g.mot [to] + " ") ;
	}
    }

    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 ;
		}
	    }
	}
    }

    // retourne l'indice d'un sommet le plus eloigne possible de x
    static int bfsIteratif (Graphe g, int x) {
	FIFO aVisiter = new FIFO (x) ;
	g.dejaVu [x] = true ;
	g.distance [x] = 0 ;
	int excentricite = 0 ;
	int somLoin = x ;
	while (FIFO.nonVide (aVisiter)) {
	    int i = FIFO.supprimer (aVisiter) ;
	    int dist = g.distance [i] ;
	    if (dist > excentricite) {
		excentricite = dist ;
		somLoin = i ;
	    }
	    //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 ;
		    g.distance [y] = dist + 1 ;
		    FIFO.ajouter (aVisiter, y) ;
		    g.pere[y] = i ;
		}
	    }
	}
	return somLoin ;
    }
    
    static int sommetExcentrMax (Graphe g) {
	int excMax = -1 ;
	int somExcMax = -1 ;
	int loinMax = -1 ;
	for (int x = 0 ; x < g.nb ; ++x) {
	    initVisit (g) ;
	    int loin = bfsIteratif (g, x) ;
	    int exc = g.distance [loin] ;
	    if (exc > excMax) {
		excMax = exc ;
		somExcMax = x ;
		loinMax = loin ;
	    }
	}
	return somExcMax ;
    }

    
    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) ;
	Graphe g = new Graphe (new File (args[0])) ;
	lettreQuiSaute (g, 1, 1) ;
	//afficher (g) ;
	//visit (g) ;
	int sem = sommetExcentrMax (g) ;
	initVisit (g) ;
	int loin = bfsIteratif (g, sem) ;
	int dist = g.distance [loin] ;
	System.out.println (g.mot[loin] + " est a distance " + dist + " de " + g.mot [sem] + "\n") ;
	chemin (g, g.mot[sem], g.mot[loin]) ;
    }
}