|Online Judge||Problem Set||Authors||Online Contests||User|
A tragedy happened recently in your city. A patient in critical condition, who needed urgent treatment, died when being transported to a big hospital in the capital of the state. What happened was that the ambulance was held up in the traffic, due to a rock that slid onto the road. People complained with the governor, who now desires to prevent similar events in the future. Unfortunately, rock slides are very common in this state, with many mountains and sierras. Thus, in order to minimize the number of tragedies due to rock slides and other unexpected occurrences, the governor decided to create alternative routes between each city of the state and the capital. For this, it is necessary to initially identify which road segments are currently critical, that is, if they are blocked it will be caused that there are no possible paths between some city and the capital. A road segment is a course of road that connects two different cities.
Your task is to write a program for identifying these critical road segments.
The input is composed of several test cases. The first line of a test case contains two integers N and M that indicate respectively the number of the cities (2 ≤ N ≤ 100) and the number of road segments (1 ≤ M ≤ 10000). Each one of the N lines following contains the name of a city (letters only, at most 20 characters long). The first of these cities is the capital of the state. Each one of the M lines following describes a road segment, containing a pair of names of cities separated by a whitespace. Note that, as the mountains cause difficulty in construction of the roads, many road segments are one-way. A two-way segment is represented by two one-way ones. You should assume that there exists at least one path from each city to the capital. The end of the input is indicated by N = M = 0.
For each test case your program should list the critical segments, one critical segment per line. Each critical segment should be represented by two names of cities separated by a whitespace. The critical segments should be listed in the same order they appear in the input; for each segment, the cities should be listed in the same order they appear in the input. If there exist no critical segments your program should print a line containing only the word “Nenhuma” (“None”). Print a blank line after each test cases.
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
Gramado NovoHamburgo NovoHamburgo PortoAlegre RioGrande Pelotas Pelotas PortoAlegre SantaClara SanFrancisco Nenhuma
South America 2006, Brazil Subregion
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator