记录编号	202646	评测结果	AAAAAAAAAAA
题目名称	[IOI 1993][USACO]周游加拿大	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2015-11-01 17:40:55	内存使用	0.39 MiB

#include<cstdio>
#include<map>
#include<iostream>
#include<cstring>
#include<string>
#define Max(a,b) ((a)>(b)?(a):(b))
using namespace std;
map<string,int>ma;
int c[102][102];
int n,m,f[102][102];
string s1,s2,s;
int main(){
    freopen("tourus.in","r",stdin);
	freopen("tourus.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) cin>>s,ma[s]=i;
	for(int i=1;i<=m;++i){
		cin>>s1>>s2;
		c[ma[s1]][ma[s2]]=c[ma[s2]][ma[s1]]=1;
	}
	memset(f,-0x3f,sizeof(f));
	f[1][1]=1;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			for(int k=1;k<=min(i,j);++k){
				if(k==i&&i!=1||(k==j&&j!=1))continue;
                if(c[k][i]) f[i][j]=Max(f[i][j],f[k][j]+1);
				if(c[k][j]) f[i][j]=Max(f[i][j],f[i][k]+1);
			}
		}
	}
	if(f[n][n]<0) printf("1");
	else printf("%d",f[n][n]-1);
	return 0;
}