如题，wtcl。

不是讨论区里的 WA on #2；#3 显示 wrong answer Expected no sulution。

快哭了/kel

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f
const int N=1e4+10;
struct Edge{
	int u,v,w,c,f;
	Edge(int _u,int _v,int _w,int _c,int _f): u(_u),v(_v),w(_w),c(_c),f(_f){}
};
struct Graph{
	int n,m,s,t;
	vector<Edge> e;
	vector<int> g[N];
	int d[N];
	bool vis[N];
	void clear(int _n,int _m,int _s,int _t){
		n=_n,m=_m,s=_s,t=_t;
		for(int i=1;i<=n;++i) g[i].clear();
		e.clear();
	}
	void add_edge(int u,int v,int c,int w){
		//cout<<u<<" "<<v<<" "<<w<<" "<<c<<endl;
		e.push_back(Edge(u,v,w,c,0));
		e.push_back(Edge(v,u,-w,0,0));
		g[u].push_back(e.size()-2);
		g[v].push_back(e.size()-1);
	}
	bool spfa(){
		memset(vis,0,sizeof(vis));
		memset(d,0x3f,sizeof(d));
		queue<int> q;
		q.push(s);
		d[s]=0;
		vis[s]=1;
		while(!q.empty()){
			int u=q.front();
			q.pop();vis[u]=0;
			for(auto t:g[u]){
				Edge& ed=e[t];
				if(ed.c>ed.f&&d[ed.v]>d[u]+ed.w){
					d[ed.v]=d[u]+ed.w;
					if(!vis[ed.v]){
						vis[ed.v]=1;
						q.push(ed.v);
					}
				}
			}
		}
		return d[t]!=INF;
	}
	ll ret;
	ll DFS(int x,ll a){
		if(x==t||a==0) return a;
		vis[x]=1;
		ll flow=0;
		for(auto t:g[x]){
			Edge& ed=e[t];
			if(!vis[ed.v]&&d[x]+ed.w==d[ed.v]){
				int f=DFS(ed.v,min(a,1ll*(ed.c-ed.f)));
				if(f>0){
					ret+=ed.w*f;
					ed.f+=f;
					e[t^1].f-=f;
					flow+=f;
					a-=f;
					if(a==0) break;
				}
			}
		}
		if(flow==0)
			d[x]=0;
		vis[x]=0;
		return flow;
	}
	ll Dinic(){
		ll flow=0;
		while(spfa()){
			ll tf=0;
			while(1){
				ll f=DFS(s,INF);
				if(f==0) break;
				tf+=f;
			}
			if(tf==0) break;
			flow+=tf;
		}
		return flow;
	}
	void print(){
		cout<<n<<" "<<s<<" "<<t<<endl;
		for(auto p:e){
			printf("%d %d %d %d\n",p.u,p.v,p.c,p.w);
		}
		for(int i=1;i<=n;++i){
			printf("%d: ",i);
			for(auto j:g[i]) printf("%d ",j);
			puts("");
		}
	}
}g;
string s[N];
map<string,int> mp;
bool vis[N];
int n,m;
void dfs1(int u){
	cout<<s[u]<<endl;
	vis[u]=1;
	for(auto ed:g.g[u])
		if(g.e[ed].v>n&&g.e[ed].v<=2*n&&g.e[ed].c==g.e[ed].f){
			dfs1(g.e[ed].v-n);
			break;
		}
}
void dfs2(int u){
	vis[u]=1;
	for(auto ed:g.g[u])
		if(g.e[ed].v>n&&g.e[ed].v<=2*n&&g.e[ed].c==g.e[ed].f&&!vis[g.e[ed].v-n]){
			dfs2(g.e[ed].v-n);
			break;
		}
	cout<<s[u]<<endl;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		cin>>s[i];
		mp[s[i]]=i;
	}
	bool check=0;
	int S=n*2+1,T=S+1;
	g.clear(T,-1,S,T);
	for(int i=1;i<=m;++i){
		string s1,s2;
		cin>>s1>>s2;
		int x=mp[s1],y=mp[s2];
		if(x>y) swap(x,y);
		if(x==y) continue;
		if(x==1&&y==n) check=1;
		g.add_edge(x,y+n,1,0);
	}
	g.add_edge(S,n+1,0x3f3f3f3f,0);
	g.add_edge(n,T,0x3f3f3f3f,0);
	for(int i=1;i<=n;++i){
		if(i!=1&&i!=n) g.add_edge(i+n,i,1,-1);
		else g.add_edge(i+n,i,2,-1);
	}
	ll fl=g.Dinic();
	if(fl==2){
		printf("%lld\n",-g.ret-2);
		dfs1(1);
		dfs2(1);
	}
	else if(fl==1&&check){
		printf("%d\n",2);
		cout<<s[1]<<endl<<s[n]<<endl<<s[1]<<endl;
	}
	else puts("No Solution");
    return 0;
}