class Graphe {

    int nb ;            // Nombre de sommets
    Liste[] listeSucc ; // Listes d'adjacence
    String[] mot ;
    boolean[] dejaVu ; // Pour le parcours en profondeur.
    boolean[] visiteEnCours ; // Pour les cycles
    int[] succCycle ; // Successeur dans le cycle si on en trouve un

    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] ;
	visiteEnCours = new boolean [nb] ;
	succCycle = new int [nb] ;
    }

    static void afficher (Graphe g) {
	System.out.println ("digraph dico {") ;
	System.out.println ("  node [style=filled, fontcolor=red];") ;
	System.out.println ("  edge [style=bold, color=blue];") ;
	for (int i=0 ; i<g.nb ; ++i) {
	    //System.out.print ("  " + g.mot [i] + " -> { ") ;
	    //afficherSuccesseurs (g, i) ;
	    //System.out.println ("}") ;
	    //   Affichons ar^ete par ar^ete pour visualiser le cycle
	    System.out.println ("  " + g.mot [i] + " ;") ; // Signalons le sommet
	    afficherAretes (g, i) ;
	    System.out.println () ;
	}
	System.out.println ("}") ;
    }

    static void afficherAretes (Graphe g, int i) {
	for (Liste v=g.listeSucc [i] ; v!=null ; v=v.suivant) {
	    System.out.print ("  " + g.mot[i] + " -> " + g.mot [v.contenu]) ;
	    if (v.contenu == g.succCycle[i])
		System.out.print (" [color=green]") ; // Ar^ete du cycle
	    System.out.println (" ;") ;
	}
    }
  
    static void afficherSuccesseurs (Graphe g, int i) {
	for (Liste v=g.listeSucc [i] ; v!=null ; v=v.suivant)
	    System.out.print (g.mot [v.contenu] + " ") ;
    }
  
    static void lettreQuiSaute (Graphe g) {
	for (int i=0 ; i<g.nb ; ++i)
	    for (int j=0 ; 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 ;
	if (a.charAt (i) > b.charAt (i))
	//if (a.charAt (i) < b.charAt (i)) // graphe inverse pour le tri topologique
	    return false ; // version orient'ee
	++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]) 
		dfs(g, y) ;
	}
    }

    static boolean dfsCycle (Graphe g, int x) {
	g.dejaVu[x] = true ;
	g.visiteEnCours[x] = true ;
	for (Liste ls = g.listeSucc[x] ; ls != null ; ls = ls.suivant) {
	    int y = ls.contenu ;
	    g.succCycle[x] = y ; // Chemin des appels récursifs qui va éventuellement boucler
	    if (!g.dejaVu[y]) {
		if (dfsCycle (g, y))
		    return true ;
	    } else if (g.visiteEnCours[y])
		return true ;
	}
	//System.out.print (g.mot[x]) ;
	//System.out.print (" : ") ;
	//afficherSuccesseurs (g, x) ;
	//System.out.println () ;
	g.succCycle[x] = -1 ; // On n'a pas trouv'e de cycle passant par x
	g.visiteEnCours[x] = false ;
	return false ;
    }

    static void initVisit (Graphe g) {
	for (int x = 0 ; x < g.nb ; ++x) {  
	    g.dejaVu[x] = false ;
	    g.visiteEnCours[x] = false ;
	    g.succCycle[x] = -1 ;
	}
    }

    static void invTriTopologique (Graphe g) {
	initVisit (g) ;
	for (int x = 0 ; x < g.nb ; ++x)
	    if (! g.dejaVu[x]) {
		if (dfsCycle (g, x)) 
		    throw new Error ("Il y a un cycle !") ;
	    }
    }

    static void trouveCycle (Graphe g) {
	initVisit (g) ;
	for (int x = 0 ; x < g.nb ; ++x)
	    if (! g.dejaVu[x]) {
		if (dfsCycle (g, x)) {
		    // On a trouve un cycle, il faut enlever le d'ebut du chemin jusqu'au cycle
		    enleverCheminAvantCycle (g, x) ;
		    return ;
		} 
	    }
	throw new Error ("Il n'y a pas de cycle !") ;
    }

    static void enleverCheminAvantCycle (Graphe g, int x) {
	for (int i = 0 ; i < g.nb ; ++i) {  
	    g.dejaVu[i] = false ;
	}
	int prem ;
	for (prem=x ; !g.dejaVu[prem] ; prem=g.succCycle [prem]) {
	    g.dejaVu[prem] = true ;
	}
	// y est maintenant le premier sommet du cycle
	while (x != prem) {
	    int suiv = g.succCycle[x] ;
	    g.succCycle[x] = -1 ;
	    x = suiv ;
	} 
    }

    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) ;
		System.out.println () ;
	    }
    }


    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) ;
	g.listeSucc[9] = new Liste (22, g.listeSucc[9]) ;
	//System.out.println (dfsCycle (g, 0)) ;
	//invTriTopologique (g) ;
	trouveCycle (g) ;
	afficher (g) ;
    }
}