记录编号	82514	评测结果	AAAAAAAAAAA
题目名称	[IOI 1993][USACO]周游加拿大	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2013-11-24 22:30:31	内存使用	0.36 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
const int SIZEN=101;
map<string,int> citylis;
int n,m;//n是城市数m是线路数
bool c[SIZEN][SIZEN]={0};//邻接矩阵
int f[SIZEN][SIZEN]={0};
void DP(void){
	f[n][n]=1;
	int i,j,k;
	for(i=n;i>=1;i--){
		for(j=n;j>=1;j--){
			if(i==j&&i!=n) continue;
			//f[i][j]已求出
			if(f[i][j]==0) continue;
			for(k=min(i,j);k>=1;k--){
				if(c[k][j]){
					f[i][k]=max(f[i][k],f[i][j]+1);
				}
				if(c[k][i]){
					f[k][j]=max(f[k][j],f[i][j]+1);
				}
			}
		}
	}
}
void read(void){
	scanf("%d%d",&n,&m);
	int i;
	string str;
	for(i=1;i<=n;i++){
		cin>>str;
		citylis[str]=i;
	}
	string a,b;
	int u,v;
	for(i=1;i<=m;i++){
		cin>>a>>b;
		u=citylis[a],v=citylis[b];
		c[u][v]=c[v][u]=true;
	}
}
int main(){
	freopen("tourus.in","r",stdin);
	freopen("tourus.out","w",stdout);
	read();
	DP();
	if(f[1][1]==0){
		cout<<1<<endl;
		return 0;
	}
	cout<<f[1][1]-1<<endl;
	return 0;
}