Critical Route
Description
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.
Input
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.
Output
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 0Gramado NovoHamburgo
NovoHamburgo PortoAlegre
RioGrande Pelotas
Pelotas PortoAlegre
SantaClara SanFrancisco
Nenhuma
Source
South America 2006, Brazil Subregion
</p>