水题.
本质上题目要求的是一个包含 $1$，$n$ 的最大环，所以每个点只可以经过一次.
那么就拆点，然后限制每个点的经过次数就行了.
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<string>
#include<map>
using namespace std;
const int maxn=800;
const int INF=1000000+23666;
typedef long long ll;
map<string,int>idx;
string A[maxn];
int viss[maxn];
int s,t,n;
struct Edge{
int from,to,cap,cost;
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),cost(f){}
};
vector<Edge>edges;
vector<int>G[maxn];
struct MCMF{
int d[maxn],inq[maxn],a[maxn],flow2[maxn];
queue<int>Q;
ll ans=0;
int flow=0;
void addedge(int u,int v,int c,int f){
edges.push_back(Edge(u,v,c,f)); //正向弧
edges.push_back(Edge(v,u,0,-f)); //反向弧
int m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
int SPFA(){
for(int i=0;i<=n;++i)d[i]=INF,flow2[i]=INF;
memset(inq,0,sizeof(inq));int f=INF;
d[s]=0,inq[s]=1;Q.push(s);
while(!Q.empty()){
int u=Q.front();Q.pop();inq[u]=0;
int sz=G[u].size();
for(int i=0;i<sz;++i){
Edge e=edges[G[u][i]];
if(e.cap>0&&d[e.to]>d[u]+e.cost){
a[e.to]=G[u][i];
d[e.to]=d[u]+e.cost;
flow2[e.to]=min(flow2[u],e.cap);
if(!inq[e.to]){inq[e.to]=1;Q.push(e.to);}
}
}
}
if(d[t]==INF)return 0;
f=flow2[t];
flow+=f;
int u=edges[a[t]].from;
edges[a[t]].cap-=f;
edges[a[t]^1].cap+=f;
while(u!=s){
edges[a[u]].cap-=f;
edges[a[u]^1].cap+=f;
u=edges[a[u]].from;
}
ans+=(ll)(d[t]*f);
return 1;
}
int maxflow(){
while(SPFA());
return flow;
}
ll getcost(){return ans;}
}op;
void print(int x){
if(x==t-1)return;
int sz=G[x+1].size();
for(int i=0;i<sz;++i){
int e=G[x+1][i];
if(e%2==0&&edges[e].cap==0&&!viss[e]){
print(edges[e].to);
cout<<A[x]<<endl;
return;
}
}
}
int main(){
int N,M;cin>>N>>M;
int cnt=1;
for(int i=1;i<=N;++i){
string s;cin>>s;idx[s]=cnt;A[cnt]=s;
if(i==1||i==N)op.addedge(cnt,cnt+1,2,0);
else op.addedge(cnt,cnt+1,1,0);
cnt+=2;
}
n=cnt-1,s=1,t=n;
for(int i=1;i<=M;++i)
{
string a,b;cin>>a>>b;
int ax=idx[a],bx=idx[b];
if(ax<bx)op.addedge(ax+1,bx,1,-1);
else op.addedge(bx+1,ax,1,-1);
}
int F=op.maxflow();
ll ans=op.getcost();
if(F!=2)
{
if(ans==-1){
cout<<2<<endl;
cout<<A[s]<<endl;
cout<<A[t-1]<<endl;
cout<<A[s]<<endl;
return 0;
}
else {cout<<"No Solution!"<<endl;return 0;}
}
cout<<-ans<<endl;
int tr=s;
cout<<A[s]<<endl;
do
{
++tr;
int sz=G[tr].size();
for(int i=0;i<sz;++i){
int e=G[tr][i];
if(e%2==0&&edges[e].cap==0){tr=edges[e].to,viss[e]=1;break;}
}
if(tr!=t)cout<<A[tr]<<endl;
}while(tr!=t);
print(s);
return 0;
}