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.|

ROTA - Rota crítica

Uma tragédia aconteceu recentemente em sua cidade. Um paciente em condição crítica, que necessitava tratamento urgente, morreu enquanto era transportado para um grande hospital da capital do estado. O que ocorreu foi que a ambulância ficou presa no trânsito, devido a uma rocha que deslizou na estrada. A população reclamou com o governador, que agora deseja evitar acontecimentos similares no futuro. Infelizmente, deslizamentos de rochas são muito comuns nesse estado, com muitas montanhas e serras. Assim, para minimizar o número de tragédias devidas a deslizamentos de rochas e outros imprevistos, o governador decidiu criar rotas alternativas entre cada cidade do estado e a capital. Para isso, é necessário inicialmente identificar quais segmentos de estradas são atualmente críticos, isto é, se bloqueados causam que não haja caminho possível entre alguma cidade e a capital. Um segmento de estrada é um trecho de estrada que liga duas cidades distintas.

Sua tarefa é escrever um programa para identificar esses segmentos críticos de estradas.

Entrada

A entrada é composta de vários casos de testes. A primeira linha de um caso de teste contém dois inteiros N e M que indicam respectivamente o número de cidades (2 ≤ N ≤ 100) e o número de segmentos de estrada (1 ≤ M ≤ 10000). Cada uma das N linhas seguintes contém o nome de uma cidade (apenas letras minúsculas e maiúsculas, comprimento máximoa de 20 caracteres). A primeira dessas cidades é a capital do estado. Cada uma das M linhas seguintes descreve um segmento de estrada, contendo um par de nomes de cidades separados por um espaço em branco. Note que, como as montanhas causam dificuldade na construção de estradas, muitos segmentos de estrada são de mão unica. Um segmento com duas mãos é representado por dois trechos de mão unica. Você deve supor que existe ao menos um caminho de cada cidade para a capital. O final da entrada é indicado por N = M = 0.

Saída

Para cada caso de teste seu programa deve listar os segmentos críticos, com um segmento crítico por linha. Cada segmento crítico deve ser representado por dois nomes de cidades separados por um espaço em branco. Os segmentos críticos de estrada devem ser listados na mesma ordem em que aparecem na entrada; para cada segmento, as cidades devem ser listadas na mesma ordem em que aparecem na entrada. Se não existir nenhum segmento crítico seu programa deve imprimir uma linha contendo apenas a palavra “Nenhuma”. Imprima uma linha em branco após cada caso de teste.

Exemplo de entrada

6 10
PortoAlegre
Gramado
Canela
NovoHamburgo
Pelotas
RioGrande
Canela Gramado
Canela NovoHamburgo
Gramado NovoHamburgo
NovoHamburgo PortoAlegre
PortoAlegre NovoHamburgo
RioGrande Pelotas
Pelotas PortoAlegre
PortoAlegre Pelotas
Pelotas RioGrande
NovoHamburgo Canela
3 5
Sacramento
SanFrancisco
SantaClara
SanFrancisco Sacramento
Sacramento SantaClara
SantaClara SanFrancisco
SanFrancisco Sacramento
Sacramento SanFrancisco
3 4
Recife
Olinda
Paulista
Olinda Recife
Paulista Recife
Olinda Paulista
Paulista Olinda
0 0

Saída para o exemplo de entrada

Gramado NovoHamburgo
NovoHamburgo PortoAlegre
RioGrande Pelotas
Pelotas PortoAlegre

SantaClara SanFrancisco

Nenhuma

Adicionado por:Wanderley Guimarăes
Data:2009-09-30
Tempo limite:0.460s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Primeira fase da Maratona de Programação - 2006

hide comments
2011-09-22 23:36:35 thiagojobson [UERN]
Esse enunciado é meio confuso com relaçăo a estradas duplicadas e estradas de măo dupla. Vocę deve tratar como segmentos diferentes.

Last edit: 2011-09-22 23:40:10
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.