```cpp
#include<cstdio>
#include<queue>
#include<cstring>
#include<queue>
#include<algorithm>
#include<string>
#include<map>
#include<iostream>
#define INF 2147483647
#define I inline
#define R register
using namespace std;
queue<int> f;
map<string,int> id;
map<int,string> ch;
int n,m,ans,len=-1,st,ed;
struct node{int x,y,c,d,next;} a[10000];
int last[10000],dis[10000],pre[10000],pos[10000],p[10000];
bool bz[10000],flag[1000];
I void ins(int x,int y,int c,int d)
{
a[++len].x=x;a[len].y=y;a[len].c=c;a[len].d=d;a[len].next=last[x];last[x]=len;
}
I bool spfa()
{
memset(bz,true,sizeof(bz));
bz[st]=false;
memset(dis,63,sizeof(dis));
dis[st]=0;
p[st]=INF;
f.push(st);
while(!f.empty())
{
int x=f.front();
bz[x]=true;
for(R int i=last[x];i>=0;i=a[i].next)
{
int y=a[i].y;
if(a[i].c>0&&dis[y]>dis[x]+a[i].d)
{
dis[y]=dis[x]+a[i].d;
pos[y]=x;
pre[y]=i;
p[y]=min(p[x],a[i].c);
if(bz[y])
{
f.push(y);
bz[y]=false;
}
}
}
f.pop();
}
return dis[ed]<1061109567;
}
I int flow()
{
int ans=0;
while(spfa())
{
ans+=p[ed]*dis[ed];
for(R int i=ed;i!=st;i=pos[i])
{
a[pre[i]].c-=p[ed];
a[pre[i]^1].c+=p[ed];
}
}
return -ans==2?-ans:-ans-2;
}
I void dfs1(int x)
{
if(x==n) return;
for(R int i=last[x];i!=st;i=a[i].next)
if(flag[a[i].y]&&(!(i&1))&&((!a[i].c&&a[i].d<=0)||(a[i].c==1&&a[i].d>=0)))
{
flag[x]=false;
if(a[i].y>=1&&a[i].y<=n) cout<<ch[a[i].y]<<endl;
dfs1(a[i].y);
return;
}
}
I void dfs2(int x)
{
for(R int i=last[x];i!=st;i=a[i].next)
if(flag[a[i].y]&&((i&1))&&((!a[i].c&&a[i].d<=0)||(a[i].c==1&&a[i].d>=0)))
{
flag[x]=false;
if(a[i].y>=1&&a[i].y<=n) cout<<ch[a[i].y]<<endl;
dfs2(a[i].y);
return;
}
}
int main()
{
char s1[100],s2[100];
int t1,t2;
scanf("%d %d",&n,&m);
st=0,ed=n*2+1;
memset(last,-1,sizeof(last));
ins(1,n+1,1,-1),ins(n+1,1,0,1);
ins(n,n+n,1,-1),ins(n+n,n,0,1);
ins(st,1,2,0),ins(1,st,0,0);
ins(n*2,ed,2,0),ins(ed,n*2,0,0);
for(R int i=1;i<=n;i++)
{
scanf("%s",s1+1);
id[s1+1]=i;
ch[i]=s1+1;
ins(i,i+n,1,-1),ins(i+n,i,0,1);
}
for(R int i=1;i<=m;i++)
{
scanf("%s %s",s1+1,s2+1);
t1=id[s1+1],t2=id[s2+1];
ins(t1+n,t2,1,0),ins(t2,t1+n,0,0);
}
ans=flow();
if(!ans)
{
printf("No Solution!");
return 0;
}
printf("%d\n",ans);
memset(flag,true,sizeof(flag));
cout<<ch[1]<<endl;
dfs1(1);
dfs2(n);
cout<<ch[1];
}
```
by Mark_ZZY @ 2018-03-19 13:36:19
超时
by Mark_ZZY @ 2018-03-19 13:36:30