from sys import argv
from string import ascii_lowercase
lowercase = frozenset(ascii_lowercase)

if len(argv) > 1:
    dictionary_name = argv[1]
else:
    dictionary_name = "/usr/share/dict/words"

dictionary = frozenset(
    word.rstrip()
    for word in file(dictionary_name)
    if lowercase.issuperset(word.rstrip())
    )

def test_word(word, candidates):
    if len(word) < 2:
        if word in "ia": # only interested in final 1-letter words "I" and "A"
            yield []
    else:
        for i in range(len(word)):
            check_word = word[:i] + word[i+1:]
            if check_word in candidates:
                for smaller_matches in test_word(check_word, candidates):
                    yield [check_word] + smaller_matches

maxlen = 5 # default to something low
longest_chains = set()
for word in dictionary:
    if len(word) < maxlen: continue # don't look at lesser words
    for results in test_word(word, dictionary):
        results = [word] + results
        new_maxlen = len(results)
        if new_maxlen > maxlen:
            maxlen = new_maxlen
            longest_chains = set([tuple([word] + results)])
        elif new_maxlen == maxlen:
            longest_chains.add(tuple(results))

for result in sorted(longest_chains):
    print("%i: %s" % (
        len(result),
        ' '.join(w.upper() for w in result),
        ))