Problem B
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 5000$, 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 $1000$ 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.

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