Problema C - Encontros no Metro
Um grupo de amigos resolveu encontrar-se para conversar um pouco sobre as últimas novidades. Como a cidade onde moram tem disponível um Metropolitano, decidiram ser esse o meio de transporte a utilizar para se deslocarem.
Como são muito preguiçosos, querem todos perder o menor tempo possível no metro. Assim, decidiram encontrar-se na estação de metro que os fizesse percorrer a menor distância possível (medida em número de estações). Mas não adianta um deles só ter de andar 3 estações, se outro tem de andar por exemplo 40 estações. O que eles querem é algo que agrade a todos, e portanto, querem escolher a estação que minimize a distância ao amigo que está mais longe dela. Assim, por exemplo, se tivermos três amigos e duas estações alternativas, uma a distâncias 2, 3 e 10 deles, e outra a distâncias 7, 8 e 9, eles devem escolher esta segunda opção, pois nela o amigo que anda mais percorre apenas 9 estações (contra os 10 que o amigo mais longínquo teria de percorrer na primeira alternativa).
Será que podes ajudá-los a encontrar essa estação óptima, que corresponda à propriedade descrita?
Escreve um programa que dado um mapa de um metro e as localizações de um grupo de amigos nessa rede de metro, determina qual a estação a escolher para minimizar o número de estações que no máximo algum deles terá de percorrer para se encontrarem todos nessa mesma estação.
Na primeira linha de input vem um número inteiro L indicando o número de linhas de metro a considerar (1 ≤ L ≤ 100).
Seguem-se L linhas, representando cada uma das linhas de metro. Cada uma delas contém um número, indicando o número de estações de metro nessa linha (no máximo 500), seguido das estações na ordem em que estão na linha (nota que se pode andar nos dois sentidos em qualquer linha e que uma estação apenas pode aparecer uma única vez na mesma linha).
Depois vem uma linha com um único número F indicando quantos amigos se querem encontrar, seguida de F, cada uma com o nome da estação onde o respectivo amigo se encontra (2 ≤ F ≤ 1000).
Espreita o exemplo de input para perceberes melhor esta especificação.
Os nomes das estações e das linhas são constituídos unicamente por letras minúsculas, e têm no máximo 30 caracteres.
O output é constituído por uma única linha, contendo o nome da estação que minimiza a máxima distância (em número de estações) a percorrer por qualquer um dos amigos para se encontrarem todos nessa estação.
Se houverem várias estações que correspondem a esse mínimo, deves escrever o nome da menor delas em termos alfabéticos.