Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

JUKEBOX - Jukebox

Os juízes ICPC estão preparando um festa para a cerimônia de abertura. Para a festa, eles pretendem adicionar um playlist com algumas músicas para o software jukebox (um simples MP3 player). Entretanto, existem muitas músicas no computador, isso dificulta encontrar aquelas que eles querem adicionar. Como conseqüência, eles precisam usar algumas buscas muitas vezes.

Nesta jukebox, quando você pesquisa por uma string s, o software retorna todas músicas cujos títulos ou nomes de artistas contém s como uma substring. A string s é uma substring da string t se t contém todos os caracteres de s como uma seqüência contigua (por exemplo, 'bc' é uma substring de 'abcd', mas 'ac' não é). Para salvar o tempo precioso deles, enquanto procuram por uma música, eles sempre usam uma string de ouro da música, isto é, uma das mais curtas strings que retornam de uma pesquisa como resultado somente a música que eles querem.

Neste exemplo, uma possível string de ouro para a música 'johnnatan' é 'ta'. Note que 'ta' não é uma substring do nome de outra música nem é uma substring do nome do artista de outra música. Note também que não existem strings de tamanho igual a 1 que podem identificar unicamente a música 'johnnatan'.

Eles descobriram que se eles removem o campo artista de algumas músicas eles podem obter strings de ouro menores. Para a música 'john', não existe nenhuma string de ouro. Entretanto, se removermos o campo artista de todas as outras músicas, a string 'c' se torna a string de ouro para a música 'john'.

Dada uma lista de músicas (cada música com nome e artista), sua tarefa é determinar a soma mínima do tamanho das strings de ouro para todas as músicas que podem ser obtidas se em algumas removermos o campo artista. Na figura acima, você pode ver um possível melhor resultado com as strings de ouro em negrito. A soma mínima dos tamanhos das strings de ouro neste caso é 10.

Entrada

A entrada contém vários casos de teste. A primeira linha de cada caso de teste contém um inteiro N (1<=N<=30), que indica o número de músicas. A seguir, existirão N pares de linhas (2*N linhas), um par para cada música. A primeira linha de um par contém o número da música, a linha conterá o nome da artista. Ambos, nome de artista e música, são strings contendo somente letras minúsculas e sobrescritos e terão no mínimo 1 e no máximo 30 caracteres. Existirão no máximo 6 artistas diferentes na lista. O fim da entrada é dado por N=0.

Saída

Para cada caso de teste seu programa deve produzir uma linha simples com a soma mínima dos tamanhos das strings de ouro. Você pode assumir que sempre existirá uma solução.


Exemplo de entrada 8 a_flor los_hermanos anna_julia los_hermanos quem_sabe los_hermanos pierrot los_hermanos azedume los_hermanos johnny massacration johnnatan massacration john massacration 4 c axc b axc d cc xc cc 0

Exemplo de saída 10 5


Adicionado por:Wanderley Guimarăes
Data:2008-12-27
Tempo limite:1.734s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL
Origem:Final Sul-Americana da Maratona de Programação da ACM 2006

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.