P2747 [USACO5.4] Canada Tour

You have won a contest held by an airline, and the prize is a ticket for a tour of Canada. The trip starts at the westernmost city served by this airline, then you keep traveling from west to east until you reach the easternmost city, and then travel from east to west back to the starting city. Except for the starting city, each city may be visited at most once, because the starting city must be visited twice (at the beginning and at the end). You are not allowed to use flights of other airlines or any other means of transportation. Given the list of cities served by this airline and the list of direct flights between pairs of cities, find a route that visits as many cities as possible while satisfying the above conditions. In other words, you must start from the first city in the list, reach the last city in the list, and then return to the first city.

Line $1$: The number of cities served by the airline $N$ and the number of direct flights to be listed $V$. $N$ is a positive integer not greater than $100$. $V$ is any positive integer. Lines $2 \sim N+1$: Each line contains the name of a city served by the airline. The cities are listed from west to east. No two cities lie on the same meridian. Each city name is a string of at most $15$ bytes, consisting of letters of the Latin alphabet; city names contain no spaces. Lines $N+2 \sim N+2+V-1$: Each line contains two city names (chosen from the list above), separated by a space, indicating a bidirectional direct flight between the two cities.

Line $1$: $M$, the number of distinct cities visited by the optimal route. If no route can be found, output `1`.

The problem statement is translated from NOCOW. USACO Training Section 5.4. Translated by ChatGPT 5