记录编号	99651	评测结果	WWWWWWWWWW
题目名称	[网络流24题] 航空路线	最终得分	0
用户昵称	（ˇˍˇ） ～耶稣	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2014-04-29 17:42:15	内存使用	0.34 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<queue>
#include<iostream>
using namespace std;

char name[105][20];
int n,m,ver[2000],edge[2000],edge1[2000],last[2000],val[2000],p[205];
int st,ed,s,maxflow,ans,dis[205],pre[205];
queue<int> q;
bool v[205],vin[205],flag;

void add(int ff,int tt,int flow,int ww){
	s++;
	ver[s]=tt;
	last[s]=p[ff];
	edge[s]=flow;
	val[s]=ww;
	p[ff]=s;
}

bool bfs(){
	int x,i;
	while (!q.empty()) q.pop();
	q.push(st);
	memset(v,0,sizeof(v));
	memset(dis,200,sizeof(dis));
	dis[st]=0;
	while (!q.empty()){
		x=q.front();q.pop();v[x]=0;
		for (i=p[x];i;i=last[i]){
			if (edge[i] && dis[ver[i]]<dis[x]+val[i]){
				dis[ver[i]]=dis[x]+val[i];
				pre[ver[i]]=i;
				if (!v[ver[i]]){
					v[ver[i]]=1;
					q.push(ver[i]);
				}
			}
		}
	}
	if (dis[ed]>0) return 1;
	return 0;
}

void update(){
	int now,i;
	now=ed;
	maxflow++;
	ans+=dis[ed];
	while (now!=st){
		i=pre[now];
		edge[i]-=1;
		edge[i ^ 1]+=1;
		now=ver[i ^ 1];
	}
}

void dfs(int x){
	v[x]=1;
	printf("%s\n",name[x]);
	int i;
	for (i=p[x];i;i=last[i]){
		if (vin[i] && !v[ver[i]] && ver[i]<=n) dfs(ver[i]);
	}
}
int main(){
	freopen("airl.in","r",stdin);
	freopen("airl.out","w",stdout);
	
	char s1[20],s2[20];
	int i,ff,tt;
	
	s=1;
	memset(p,0,sizeof(p));
	scanf("%d%d",&n,&m);
	getchar();
	for (i=1;i<=n;i++){
	  scanf("%s",&name[i]);	
	}
	
	st=1;
	ed=n+n;
	add(st,st+n,2,0);
	add(st+n,st,0,0);
	add(n,ed,2,0);
	add(ed,n,0,0);
	for (i=2;i<n;i++){
		add(i,i+n,1,0);
		add(i+n,i,0,0);
	}
	flag=0;
	for (i=1;i<=m;i++){
		scanf("%s%s",&s1,&s2);
		for (ff=1;ff<=n;ff++)
		 if (!strcmp(s1,name[ff]))  break;
		for (tt=1;tt<=n;tt++)
		 if (!strcmp(s2,name[tt]))  break;
		 if (ff>tt) swap(ff,tt);
	
		 add(ff+n,tt,1,1);
		 add(tt,ff+n,0,-1);
		 if (ff==1 && tt==n) flag=1;
	}
	
	for (i=1;i<=s;i++){
		edge1[i]=edge[i];
	}
	ans=0;
	maxflow=0;
	while (bfs()){
		update();
	}
	if (maxflow!=2){
		if (flag) printf("%d\n",2);
		else	printf("%s\n","No Solution!");
		return 0;
	} 
	printf("%d\n",ans);
/*	memset(vin,0,sizeof(vin));
	memset(v,0,sizeof(v));
	for (i=1;i<=s;i++){
		if (edge1[i]!=edge[i]) vin[i]=1;
	}
	dfs(1);
	printf("%s\n",name[1]);*/
	return 0;
}