题目描述

给定一张航空图，图中顶点代表城市，边代表$\red{2}$城市间的直通航线。现要求找出一条满 足下述限制条件的且途经城市最多的旅行路线。

(1)从最西端城市出发，单向从西向东途经若干城市到达最东端城市，然后再单向从东 向西飞回起点(可途经若干城市)。

(2)除起点城市外，任何城市只能访问$\red{1}$次。

编程任务： 对于给定的航空图，试设计一个算法找出一条满足要求的最佳航空旅行路线。

输入格式

文件第$\red{1}$ 行有$\red{2}$个正整数$\red{N}$ 和$\red{V}$，$\red{N}$ 表示城市数，$\red{N<100}$， $\red{V}$ 表示直飞航线数。接下来的$\red{N}$行中每一行是一个城市名，可乘飞机访问这些城市。城市名 出现的顺序是从西向东。也就是说，设$\red{i}$,$\red{j}$ 是城市表列中城市出现的顺序，当$\red{i>j}$ 时，表示 城市$\red{i}$ 在城市$\red{j}$ 的东边，而且不会有$\red{2}$ 个城市在同一条经线上。城市名是一个长度不超过 $\red{15}$ 的字符串，串中的字符可以是字母或阿拉伯数字。例如，$\red{AGR34}$或$\red{BEL4}$。 再接下来的$\red{V}$ 行中，每行有$\red{2}$ 个城市名，中间用空格隔开，如 city1 city2 表示city1 到city2 有一条直通航线，从city2 到city1 也有一条直通航线。

输出格式

文件第$\red{1}$ 行有$\red{2}$个正整数$\red{N}$ 和$\red{V}$，$\red{N}$ 表示城市数，$\red{N<100}$， $\red{V}$ 表示直飞航线数。接下来的$\red{N}$行中每一行是一个城市名，可乘飞机访问这些城市。城市名 出现的顺序是从西向东。也就是说，设$\red{i}$,$\red{j}$ 是城市表列中城市出现的顺序，当$\red{i>j}$ 时，表示 城市$\red{i}$ 在城市$\red{j}$ 的东边，而且不会有$\red{2}$ 个城市在同一条经线上。城市名是一个长度不超过 $\red{15 }$的字符串，串中的字符可以是字母或阿拉伯数字。例如，$\red{AGR34}$或$\red{BEL4}$。 再接下来的$\red{V}$ 行中，每行有$\red{2}$ 个城市名，中间用空格隔开，如 city1 city2 表示city1 到city2 有一条直通航线，从city2 到city1 也有一条直通航线。

样例

输入样例

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