Problema B - O Último a Rir

Hoje em dia, toda a gente tem telemóvel e envia SMS por tudo e por nada. Se me contarem uma anedota gira é da praxe mandá-la logo a todos os meus amigos que estejam na lista de contactos do meu telemóvel. Cada um dos meus amigos, achando piada à anedota, reenviá-la-á aos seus amigos (se tiver cuidado, não ma mandará de volta...) e assim sucessivamente. Ao fim de algum tempo, todos os habitantes do planeta conhecerão a anedota. Ao fim de quanto tempo, exactamente?

Não temos dados nem poder computacional para calcular isso, mas, se em vez de considerar toda a espécie humana nos limitarmos a um subconjunto não muito grande, já conseguiremos qualquer coisa. Neste caso, concretamente, dados um conjunto de pessoas e a lista de contactos de cada uma delas, queremos descobrir, para uma anedota enviada originalmente por uma dessas pessoas, qual é a última pessoa a ler a anedota e quanto tempo após a primeira transmissão ela a lerá. Admitimos, o que é uma simplificação deveras grosseira, que toda a gente leva uma unidade de tempo a reencaminhar a SMS para todos os seus contactos, que o faz imediatamente após a ter recebido e que o tempo de transmissão é nulo.

O Problema

Escreva um programa para calcular a última pessoa a receber a anedota via SMS e o número de unidades de tempo que a SMS levou até chegar a essa pessoa, a partir de uma pessoa dada.

Input

Na primeira linha do input vem um número inteiro, N, o número de pessoas no nosso "universo", 0 < N ≤ 1024. Em cada uma das N linhas seguintes vem uma única cadeia de caracteres, sem espaços, representando o nome de cada uma das pessoas. Não há repetições , os nomes são escritos só com minúsculas e dígitos, e um nome nunca terá mais que 30 caracteres. Segue-se no input uma linha com um número inteiro, M, o número de pessoas cuja lista de contactos não é vazia, 0 < M &le N. Seguem-se M linhas, cada uma com vários nomes, cada linha representando uma lista de contactos. O primeiro nome de cada linha é o do dono da lista e os restantes são os nomes dos seus contactos. Todos os nomes são nomes de alguma pessoa do nosso universo.

Output

O output contém duas linhas. Na primeira vem o número de unidades de tempo que a mensagem SMS leva até chegar da primeira pessoa da lista de pessoas (cujo nome vem na segunda linha do input) à última pessoa a recebê-la. Na segunda linha vem o nome da última pessoa a receber a mensagem. No caso de haver várias "últimas" pessoas, esta segunda linha conterá os nomes de cada uma delas, por ordem alfabética, separados por um espaço. Note que pode haver pessoas que não vão receber a mensagem, mas essas não interessam.

Exemplo de Input

10
joao
paula
anabela
valdemar
carlos
goncalo
rita
miguel
vera
lucia
8
joao paula anabela miguel
paula goncalo
anabela joao carlos vera
carlos joao rita
goncalo paula rita vera
rita paula joao
vera valdemar
lucia joao

Exemplo de Output

3
rita valdemar

Selecção dos Concorrentes Portugueses
Olimpíadas Internacionais de Informática 2005

(12 de Agosto de 2005)