航空路线问题

题目描述

给定一张航空图，图中顶点代表城市，边代表两城市间的直通航线，并且不存在任何两个城市在同一条经线上。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。 1. 从最西端城市出发，单向从西向东途经若干城市到达最东端城市，然后再单向从东向西飞回起点（可途经若干城市）。 2. 除起点城市外，任何城市只能访问一次。对于给定的航空图，试设计一个算法找出一条满足要求的最佳航空旅行路线。

输入输出格式

输入格式

输入的第一行是用空格隔开的两个整数，分别代表航空图的点数 $n$ 和边数 $v$。第 $2$ 到第 $(n + 1)$ 行，每行一个字符串，第 $(i + 1)$ 行的字符串代表从西向东第 $i$ 座城市的名字 $s_i$。第 $(n + 2)$ 到第 $(n + v + 1)$ 行，每行两个字符串 $x, y$，代表城市 $x$ 和城市 $y$ 之间存在一条直通航线。

输出格式

**本题存在 Special Judge**。请首先判断是否存在满足要求的路线，若存在，请给出一种旅行的方案。如果存在路线，输出格式为： - 请在第一行输出一个整数 $m$，代表途径最多的城市数。 - 在第 $2$ 到第 $(m + 2)$ 行，每行一个字符串，第 $(i + 1)$ 行的字符串代表旅行路线第 $i$ 个经过的城市的名字。请注意第 $1$ 和第 $m$ 个城市必然是出发城市名。否则请输出一行一个字符串 ``No Solution!``。

输入输出样例

输入样例 #1

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

输出样例 #1

7
Vancouver
Edmonton
Montreal
Halifax
Toronto
Winnipeg
Calgary
Vancouver

说明

**数据规模与约定** 对于 $100\%$ 的数据，保证 $1 \leq n < 100$，$1 \leq v \leq \frac{n \times (n - 1)}{2}$，$s_i$ 的长度不超过 $15$，且仅可能包含大小写字母与数字，$x, y$ 一定是输入中给出的城市名，且不会有同一组 $x, y$ 被给出两次。