题目描述

你赢得了一场航空公司举办的比赛，奖品是一张加拿大环游机票。旅行在这家航空公司开放的最西边的城市开始，然后一直自西向东旅行，直到你到达最东边的城市，再由东向西返回，直到你回到开始的城市。除了旅行开始的城市之外，每个城市只能访问一次，因为开始的城市必定要被访问两次（在旅行的开始和结束）。 当然不允许使用其他公司的航线或者用其他的交通工具。 给出这个航空公司开放的城市的列表，和两两城市之间的直达航线列表。找出能够访问尽可能多的城市的路线，这条路线必须满足上述条件，也就是从列表中的第一个城市开始旅行，访问到列表中最后一个城市之后再返回第一个城市。

输入格式：

第 1 行: 航空公司开放的城市数 $N$ 和将要列出的直达航线的数量 $V$。

接下来 $N$ 行，每行包含一个城市的名称，这些城市是按照自西向东的顺序给出的，没有任何两个城市位于同一经线上。

每个城市的名字都是一个长度不超过 15 的字符串，字符串中可能包含数字和拉丁字母，城市名称中不会出现空格。

接下来 $𝑉$ 行，每行包含两个城市名称，表示这两个城市之间存在直达双向航班。

输出格式：

Line 1: 按照最佳路线访问的不同城市的数量 $M$。 如果无法找到路线，输出 $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

7

提示

$1 \leq N \leq 100$

$1 \leq V \leq 1200$