Description

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.

Input Format

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$.

Output Format

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!.

8 9
Vancouver
Yellowknife
Edmonton
Calgary
Winnipeg
Toronto
Montreal
Halifax
Vancouver Edmonton
Vancouver Calgary
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife
Edmonton Calgary

7
Vancouver
Edmonton
Montreal
Halifax
Toronto
Winnipeg
Calgary
Vancouver 

Hint

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