class Graphe {

    int nb ;            // Nombre de sommets
    Liste[] listeSucc ; // Listes d'adjacence
    String[] mot ;
    boolean[] dejaVu ; // Pour le parcours en profondeur.
    int numCourant ;
    int[] num ; // num'erotation au fur et `a mesure de la dfs
    int[] attache ; // num'ero du point d'attache
    Pile pileVisite ; // Pour afficher les composantes bi-connexes
    Pile pileArcsSources ; // Pour afficher les arcs des
    Pile pileArcsDests ; //      composantes bi-connexes

    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] ;
	num = new int [nb] ;
	attache = new int [nb] ;
	pileVisite = new Pile () ;
	pileArcsSources = new Pile () ;
	pileArcsDests = new Pile () ;
    }

    static void afficher (Graphe g) {
	System.out.println ("graph 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] + " -- { ") ;
	    for (Liste v=g.listeSucc [i] ; v!=null ; v=v.suivant)
		System.out.print (g.mot [v.contenu] + " ") ;
	    System.out.println ("}") ;
	}
	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, boolean depart, int pere) {
	g.dejaVu[x] = true ;
	g.num[x] = g.numCourant ;
	++g.numCourant ;
	Pile.empiler (g.pileVisite, x) ;
	g.attache[x] = g.num[x] ;
	//System.out.print (g.mot[x] + " ") ;
	int nbFils = 0 ;
	boolean articulation = false ;
	for (Liste ls = g.listeSucc[x] ; ls != null ; ls = ls.suivant) {
	    int y = ls.contenu ;
	    if (!g.dejaVu[y] || (g.num[y] < g.num[x] && y != pere)) {
		Pile.empiler (g.pileArcsSources, x) ; // on empile l'arc x -> y
		Pile.empiler (g.pileArcsDests, y) ;
	    }
	    if (!g.dejaVu[y]) {
		++nbFils ;
		dfs(g, y, false, x) ;
		if (g.attache[y] < g.attache[x])
		    g.attache[x] = g.attache[y] ;
		articulation = articulation || (!depart && g.attache[y] == g.num[x]) ;
		if (depart || (g.attache[y] == g.num[x]))
		    //printComposanteBiconnexe (g, x) ;
		    printArcsComposanteBiconnexe (g, x, y) ;
	    } else if (g.num[y] < g.attache[x])
		g.attache[x] = g.num[y] ;
	}
	articulation = articulation || (depart && nbFils > 1) ;
	if (articulation)
	    System.out.println ("  " + g.mot [x] + " [fillcolor=green] ;") ; // Signalons les points d'articulation
	else
	    System.out.println ("  " + g.mot [x] + " ;") ; // Signalons les sommets
	//if (articulation)
	//    System.out.println ("Articulation: " + g.mot[x]) ;
	//if (depart && nbFils == 0) // Sommet isol'e
	//    printComposanteBiconnexe (g, x) ;
	if (depart)
	    Pile.depiler (g.pileVisite) ; // M'enage dans la pile
    }

    static void printArcsComposanteBiconnexe (Graphe g, int x, int y) {
	double ton = Math.random () ; // Plus facile de colorier au hasard que
                                      //  de bien r'epartir les couleurs
	double sat = .2 + .8 * Math.random () ;
	double lum = .2 + .8 * Math.random () ;
	int xx, yy ;
	do {
	    xx = Pile.depiler (g.pileArcsSources) ;
	    yy = Pile.depiler (g.pileArcsDests) ;
	    System.out.print ("  " + g.mot[xx] + " -- " + g.mot[yy]) ;
	    System.out.println ("  [color=\"" + ton + "," + sat + "," + lum + "\"] ;") ;
	} while (xx != x || yy != y) ;
	System.out.println () ;
    }

    static void printComposanteBiconnexe (Graphe g, int x) {
	int y ;
	do {
	    y = Pile.depiler (g.pileVisite) ;
	    System.out.print (g.mot[y] + " ") ;
	} while (y != x) ;
	System.out.println () ;
	Pile.empiler (g.pileVisite, x) ;
    }

    static void visit (Graphe g) {
	g.numCourant = 0 ;
	System.out.println ("graph dico {") ;
	System.out.println ("  node [style=filled, fontcolor=red];") ;
	System.out.println ("  edge [len=2, style=bold, color=blue];") ;
	for (int x = 0 ; x < g.nb ; ++x) {
	    g.dejaVu[x] = false ;
	    g.num[x] = -1 ;
	    g.attache[x] = -1 ;
	}
	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, true, -1) ;
		//System.out.println () ;
	    }
	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) ;
	// java Graphe | egrep '(lion|pion|paon|pain|paix|poix|poux|pour|peur)'
	lettreQuiSaute (g) ;
	//afficher (g) ;
	visit (g) ;
    }
}