Maximal Canadian Tour

You have won an airline competition whose prize is a round‐trip ticket across Canada. The journey must start in the westernmost city served by the airline (the first city in the given list), travel strictly from west to east until reaching the easternmost city (the last city in the list), and then return strictly from east to west until arriving back at the starting city. Except for the starting city which is visited twice (at the beginning and at the end), every other city can be visited at most once. Only the flights operated by this airline may be used.

Given a list of cities (in west-to-east order) and a list of direct flights between pairs of these cities, determine a route that visits as many cities as possible while satisfying the above conditions. The route must begin with the first city, reach the last city by only taking flights that go to cities further east (i.e. with a higher index in the list), and then return to the first city by only taking flights that go to cities further west.

Any valid route with the maximum number of visited cities will be accepted. If no such round‐trip route exists, output 0.

inputFormat

The input consists of several lines:

• The first line contains two integers n and m, where n is the number of cities and m is the number of direct flights.
• The second line contains n space-separated strings representing the cities in order from west to east. The first city is the starting city and the last city is the easternmost city.
• Each of the next m lines contains two space-separated strings U and V, indicating that there is a direct flight from city U to city V.

outputFormat

If a valid round‐trip route exists, output the route as a sequence of city names separated by a space. The route must start and end at the first city in the list, and the easternmost city (the last in the city list) must appear at the turning point. If no such route exists, output a single 0.

sample

4 5
A B C D
A B
A C
B D
C D
D A

A B D A