C++

Airlines haven't been doing so well recently. In addition to make the seats miniscule, getting rid of the individual TVs, no longer serving peanuts, killing pets, and not seating people for wearing clothes they don't like, they're also cancelling flights. They want to cancel all flights between cities A and B where the fewest passengers travel directly from A to B. However, they don't want to remove flights that would mean two cities are no longer connected by air travel (they don't care if this suddenly means you now have to take 4 flights instead of 1). Given origin and destination cities, your job is to figure out if cancelling all flights between those two cities will disconnect two previously connected cities.

Input Format

The two lines contain the cities the airline wishes to cancel flights between. The next line contains an integer n, the number of cities the airline serves. The next n lines contain a city served by the airline, followed by a colon, followed by a comma-separated list of the cities you can fly to from that city. For example:

San Francisco Los Angeles 8 San Diego: Los Angeles, San Jose Los Angeles: San Diego, San Francisco, Sacramento, San Jose San Francisco: Los Angeles, Santa Barbara, Las Vegas, Pheonix San Jose: Pheonix, San Diego, Los Angeles Sacramento: Pheonix, Los Angeles Santa Barbara: San Francisco Las Vegas: San Francisco Pheonix: San Francisco, San Jose 

Constraints

You can assume the flight graph is originally connected and is undirected - i.e., if there are flights from A->B there are flights from B->A and a single edge represents both.

Output Format

A single line containing "True" or "False" indicating whether they can remove the flights. For example, for the above input:

True 

Sample Input 0

San Francisco Los Angeles 8 San Diego: Los Angeles, San Jose Los Angeles: San Diego, San Francisco, Sacramento, San Jose San Francisco: Los Angeles, Santa Barbara, Las Vegas, Pheonix San Jose: Pheonix, San Diego, Los Angeles Sacramento: Pheonix, Los Angeles Santa Barbara: San Francisco Las Vegas: San Francisco Pheonix: San Francisco, San Jose 

Sample Output 0

True