Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Critical Route
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 258Accepted: 95


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.

Sample Input

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

Sample Output

Gramado NovoHamburgo
NovoHamburgo PortoAlegre
RioGrande Pelotas
Pelotas PortoAlegre

SantaClara SanFrancisco



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