Problem D
Running MoM
The bad thing about being an international Man of Mystery (MoM) is there’s usually someone who wants to kill you. Sometimes you have to stay on the run just to stay alive. You have to think ahead. You have to make sure you don’t end up trapped somewhere with no escape.
Of course, not all MoMs are blessed with a great deal of intelligence. You are going to write a program to help them out. You are going to make sure our MoM knows what cities are safe to visit and which are not. It’s not enough to just be able to run (or fly) for one or two days, we have to guarantee that the MoM can keep running for as long as might be necessary. Given a list of regular, daily flights between pairs of cities, you are going to make sure our MoM never gets stuck in a city from which there is no escape. We’ll say there is an escape from some location if there is an infinitely long sequence of cities the MoM could fly to making one flight each day.
Input
Input starts with a number, $1 \le n \le 5\, 000$, giving the number of daily flights there are between pairs of cities. Each of the next $n$ lines contain a pair of city names separated by a space. Each city name is a string of up to $30$ characters using only characters a–z, A–Z, and underscore. A line containing the name $o$ followed by $d$ indicates that there is a one-way flight from city $o$ to city $d$ every day. There are no flights that originate from and are destined for the same city.
The description of daily flights is followed by a list of up to $1\, 000$ city names that have previously been named, one per line. The list ends at end of file.
Output
Your job is to examine the list of city names at the end and determine whether or not there is an escape from each one. For each, output the name of the city, followed by the word “safe” if there is an escape and “trapped” if there is no escape.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 Arlington San_Antonio San_Antonio Baltimore Baltimore New_York New_York Dallas Baltimore Arlington San_Antonio Baltimore New_York |
San_Antonio safe Baltimore safe New_York trapped |
