当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
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
| 时间上限 | 内存上限 |
| 1000 | 65536 |