你在一个由航空公司赞助举办的比赛中获得了胜利。
奖品是由航空公司提供的一张加拿大环游机票。
你需要从最西边的一座城市出发，从西向东进行旅行，直到最东边的城市，然后再从东向西旅行，直到回到出发城市。
除了出发城市以外，任何其他城市最多只能逗留一次，而出发城市必须恰好逗留两次（旅程开始时一次，结束时一次）。
旅程中你只能乘坐该航空公司提供的航班。
给定航空公司服务的城市列表以及成对的城市之间的直航列表，请找到一个行程，该行程可以参观尽可能多的城市并满足上述条件，从最西边的城市开始，一路游玩到最东边的城市，然后返回出发城市。
第一行包含两个整数 和 ，分别表示城市数量以及航班数量。
接下来 行，每行包含一个城市的名称，这些城市是按照自西向东的顺序给出的，没有任何两个城市位于同一经线上。
每个城市的名字都是一个长度不超过 的字符串，字符串中可能包含数字和拉丁字母，城市名称中不会出现空格。
接下来 行，每行包含两个城市名称，表示这两个城市之间存在直达双向航班。
输出最多可以参观到的城市数量。
如果无法安排行程，则输出 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
,
题目翻译来自NOCOW。
USACO Training Section 5.4