P2770 Air Route Problem

Given an airline map in which vertices represent cities and edges represent direct routes between two cities, and no two cities lie on the same meridian. Find a travel route that satisfies the following constraints and visits the maximum number of cities. 1. Start from the westernmost city, fly strictly from west to east through several cities to the easternmost city, then fly strictly from east to west back to the starting city (possibly via several cities). 2. Except for the starting city, any city may be visited at most once. For the given airline map, design an algorithm to find an optimal airline travel itinerary that meets the requirements.

The first line contains two integers separated by a space, the number of vertices $n$ and the number of edges $v$. Lines $2$ to $n + 1$: each line contains a string. The $(i + 1)$-th line gives the name $s_i$ of the $i$-th city from west to east. Lines $n + 2$ to $n + v + 1$: each line contains two strings $x, y$, indicating that there is a direct route between city $x$ and city $y$.

This problem uses Special Judge. First determine whether there exists a route that meets the requirements. If it exists, output one valid itinerary. If a route exists, output: - On the first line, output an integer $m$, the maximum number of cities visited. - Then output $m$ lines, one string per line. The $i$-th line contains the name of the $i$-th city in the itinerary. Note that the $1$-st and the $m$-th cities are necessarily the starting city. Otherwise, output a single line containing the string ``No Solution!``.

Constraints and Notes For $100\%$ of the testdata, it is guaranteed that $1 \leq n < 100$, $1 \leq v \leq \frac{n \times (n - 1)}{2}$, the length of $s_i$ does not exceed $15$ and contains only letters and digits, $x, y$ are city names given in the input, and no pair $x, y$ appears more than once. Translated by ChatGPT 5