SPOJ Brasil

O DNA é uma molécula envolvida na transmissão de caracteres hereditários e na produção de proteínas, que são os principais constituintes de seres vivos. O DNA é formado pelas bases nitrogenadas adenina (A), guanina (G), citosina (C) e timina (T).

A identificação da seqüência de bases que constitui uma determinada parte do DNA pode ajudar a descoberta da cura de doenças que atacam seres vivos. Teoricamente, a identificação do DNA pode também permitir a recriação de espécies extintas, como na estória do escritor americano Michael Crichton.

O professor de Biologia de sua escola, prof. Estevão Espilbergo, conseguiu amostras de células de uma espécie de mosquito extinto a milhares de anos, e pretende, ambiciosamente, recriar o animal a partir de seu DNA. Para isso, conseguiu que um laboratório de genômica fizesse a identificação das bases das células. No entanto, pelo estado precário das células obtidas, o resultado não foi dos melhores. O professor Estevão recebeu do laboratório duas seqüências, com a informação de que essas seqüências contêm, provavelmente, muitos "buracos", ou seja, entre uma base e outra corretamente detectadas podem existir bases não detectadas.

O prof. Estevão então decidiu combinar as duas seqüências para formar uma seqüência única, e precisa de sua ajuda.

Tarefa

Sua tarefa é escrever um programa que determine a menor seqüência que contenha, como subseqüências, as duas seqüências obtidas pelo laboratório. Dizemos que uma seqüência S1 é subseqüência de uma outra seqüência S2 se acrescentando-se alguns elementos a S1 obtém-se S2. Por exemplo, ACGT é uma subseqüência de ATCGAAT, pois basta inserir um T após o A e dois A’s após o G.

Entrada

A entrada possui vários conjuntos de teste. Cada conjunto de teste é composto por duas linhas, cada uma contendo uma seqüência S composta por caracteres 'A’, 'C’, 'G’ e 'T’. O final da entrada é indicado por uma linha contendo o caractere '#’.

Exemplo de Entrada
AAATTT
GAATCT
ACGT
ATCGAAT
#

Saída

Para cada conjunto de teste, o seu programa deve escrever três linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato "Teste n", onde n é numerado seqüencialmente a partir de 1. A segunda linha deve conter uma seqüência de comprimento mínimo que contenha as duas seqüências da entrada como subseqüências. Se houver mais de uma seqüência de comprimento mínimo, seu programa pode escrever qualquer uma delas. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplo de Saída
Teste 1
GAAATCTT

Teste 2
ATCGAAT

(esta saída corresponde ao exemplo de entrada acima)

Restrições

1 <= número de caracteres de S <= 100