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.
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.
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.
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.
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
3 rita valdemar