You have won a contest sponsored by an airline. The prize is a ticket to travel around Canada, beginning in the most western point served by this airline, then traveling only from west to east until you reach the most eastern point served, and then coming back only from east to west until you reach the starting city. You are not allowed to use any other airline or any other means of transportation. Given a list of cities served by the airline, and a list of direct flights between pairs of cities, find an itinerary which visits as many cities as possible and satisfies the above conditions beginning with the first city and visiting the last city on the list and returning to the first city. N will be a positive integer not larger than 100.
V is any positive integer.
The names are ordered from west to east in the input file.