Problem C
Loopy Cab Drivers

Image by Thomas Leuthard.

You’re a cab driver, and you regularly take passengers downtown to go pick something up from a store. Often they ask you to wait for them, but it can be impossible to find parking. When you can’t find parking, you have to drive around the city, periodically coming back to where you dropped off your passenger, so that when they come back out of the store you can pick them up again. Unfortunately, the city is is full of one-way streets, and what’s more, it’s not always possible to get from any particular point in the city to any other point, because the one-way streets may not go between two different parts.

Because you can’t always get back to where you started, when you have to wait for a passenger by driving around the city you have to stay in the regions that allow you to come back to where you dropped him/her off. Therefore, your job is to make a list of the regions which you can stay in by driving around. You don’t need to worry about being able to get to a place initially.


Input consists of the description of a city. The description starts with a line containing an integer $0 \le n \le 10\, 000$. Following this are $n$ lines, each containing a pair of store names $A$ and $B$, where $A \neq B$. The pair $A$ followed by $B$ indicates that there is some way to drive from $A$ to $B$ (in that direction). No pair of stores is listed more than once, but it is possible that a pair and its reverse may be listed. Every name is a sequence of between $1$ and $20$ letters (a–z, A–Z).


Print each group of two or more stores that can be visited together (indefinitely), one group per line. Start each group with the word ‘okay’. List the stores within each group in lexicographic order. Order the groups lexicographically as well. Finally, if there are any stores where you should NOT drive to (you cannot visit them in conjunction with at least one other store indefinitely), list them of those on the last line (in lexicographic order). Start that list with the word ‘avoid’.

The sample output indicates that you can drive forever between BahamaBucks and CVS, or between HEB and Starbucks, but if you are at OfficeDepot, you can’t go anywhere else and come back again.

Sample Input 1 Sample Output 1
Starbucks HEB
BahamaBucks CVS
CVS BahamaBucks
HEB Starbucks
BahamaBucks OfficeDepot
okay BahamaBucks CVS
okay HEB Starbucks
avoid OfficeDepot

Please log in to submit a solution to this problem

Log in