#!/usr/bin/python
#vim: foldmethod=marker fileencoding=utf-8

from __future__ import division, print_function # Kompatibilita s Py2.x

import sys, collections

## OBSLUHA ZKRATKOVNÍKŮ {{{


PRVNI = 1
POSLEDNI = 2
def redukuj(slovo):
    posledni_vyskyt = {}

    # Pole, kde si pro každou pozici ve slově pamatujeme, zda je
    # prvním a/nebo posledním výskytem příslušného písmene ve slově
    flags = [0] * len(slovo)

    for pos, znak in enumerate(slovo):
        flags[pos] = POSLEDNI
        if znak in posledni_vyskyt:
            oldpos = posledni_vyskyt[znak]
            flags[oldpos] &= ~POSLEDNI
        else:
            flags[pos] |= PRVNI

        posledni_vyskyt[znak] = pos

    return ''.join( slovo[i] for i in range(len(slovo)) if flags[i] )



def zkratky(slovo, preskocit=None):
    for i in range(len(slovo)):
        for j in range(i + 1, len(slovo)):
            zkratka = slovo[i] + slovo[j]
            if zkratka != preskocit:
                yield zkratka

# Vrátí "ty správné" sousedy pro použití při hledání zlepšujících cest,
# tedy vlastně následníky v orientované interpretaci našeho grafu.
def sousede(u):
    if isinstance(u, int):
        # zkratky() nevrací jedno velké pole zkratek, nýbrž objekt, který
        # je generuje na požádání po jedné (iterátor). To nám umožňuje
        # ukončit prohledávání předčasně a strávit jím jen tolik času,
        # kolik zkratek jsme opravdu použili. To je důležité pro dosažení
        # kýžené časové složitosti.
        return zkratky(redukovane[u], s2z.get(u))
    elif isinstance(u, str):
        if u in z2s:
            return [z2s[u]]
        else:
            return []

def vrchol_volny(u):
    if isinstance(u, int):
        return u not in s2z
    else:
        return u not in z2s

## HOPCROFT-KARP {{{

def bfs():
    vrstvy = {}
    fronta = collections.deque()

    # Prohledáváme ze všech volných slovních vrcholů
    for u in range(len(hromadka)):
        if vrchol_volny(u):
            vrstvy[u] = 0
            fronta.append(u)

    while fronta:
        u = fronta.popleft()

        vrstva = vrstvy[u]

        for soused in sousede(u):
            if soused not in vrstvy:
                vrstvy[soused] = vrstva + 1
                fronta.append(soused)
                if vrchol_volny(soused):
                    # Vrať rozvrstvení a číslo poslední vrstvy (=délku nejkratší zlepšující cesty)
                    return vrstvy, vrstva + 1

    return None, None # Nenalazena zlepšující cesta -> máme maximální párování

def invertuj_hranu(u, v):
    if isinstance(u, int): s, z = u, v
    else: s, z = v, u

    if s in s2z:
        del s2z[s]
        del z2s[z]
    else:
        s2z[s] = z
        z2s[z] = s

def dfs(u, vrstva=0):
    global znacky, vrstvy, posledni_vrstva
    if znacky[u]: return False
    znacky[u] = True


    if vrchol_volny(u) and vrstva != 0:
        return True

    for soused in sousede(u):
        if soused in vrstvy:
            vrstva_souseda  = vrstvy[soused]
        elif vrstva == posledni_vrstva - 1:
            vrstva_souseda = posledni_vrstva

        if vrstva_souseda == vrstva + 1:
            if dfs(soused, vrstva + 1):
                # Vracíme se po nalezené zlepšující cestě a invertujeme stav hran.
                invertuj_hranu(u, soused)
                return True
    return False

def faze():
    global vrstvy, posledni_vrstva
    vrstvy, posledni_vrstva = bfs()
    if vrstvy is None:
        return False

    global znacky
    znacky = collections.defaultdict(lambda: False)
    for u in range(len(hromadka)):
        if vrchol_volny(u):
            dfs(u)
    return True

### KONEC: Hopcroft-Karp }}}

hromadky = {}

for slovo in sys.stdin:
    slovo = slovo.strip()
    prvni_pismeno, zbytek = slovo[0], slovo[1:]

    if prvni_pismeno not in hromadky:
        hromadky[prvni_pismeno] = []

    hromadky[prvni_pismeno].append(zbytek)

for prvni_pismeno, hromadka in hromadky.items():
    # Každý prvek dvojice ve tvaru (číslo hrany, druhý konec).
    # Číslo hrany je potřebné, abychom si mohli udržovat, které
    # hrany jsou aktuálně v párování.
    pocet_hran = 0

    s2z = {} # mapování slov na spárované zkratky
    z2s = {} # ... a naopak

    redukovane = [ redukuj(slovo) for slovo in hromadka ]

    while faze():
        pass

    for i in range(len(hromadka)):
        if i in s2z:
            zkratka = s2z[i]
            print("%-15s %s" % (prvni_pismeno + hromadka[i], prvni_pismeno + zkratka))