以下是AC代码和hack数据

hack数据：

输入：

4 3
a
b
c
d
a b
b c
c d

错误输出：

4
a
b
c
d
a

实际输出：

No Solution!

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e6+5, M = 1e6+5;
const int MOD = 998244353, INF = 0x3f3f3f3f;
int S, T;
int h[N], e[M], f[M], w[M], ne[M], idx;
int d[N], pre[N], incf[N];
bool st[N];
void add(int a, int b, int c, int d) {
	e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx ++;
	e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx ++;
}
bool spfa() {
	memset(d, 0x3f, sizeof d);
	memset(incf, 0, sizeof incf);
	queue<int> q;
	q.push(S), d[S] = 0, incf[S] = INF;
	while(q.size()) {
		int t = q.front();
		q.pop();
		st[t] = false;

		for(int i = h[t]; ~i; i = ne[i]) {
			int j = e[i];
			if(f[i] && d[j] > d[t] + w[i]) {
				d[j] = d[t] + w[i];
				pre[j] = i;
				incf[j] = min(f[i], incf[t]);
				if(!st[j]) {
					q.push(j);
					st[j] = true;
				}
			}
		}
	}
	return incf[T] > 0;
}
void EK(int &flow, int &cost) {
	flow = cost = 0;
	while(spfa()) {
		int t = incf[T];
		flow += t, cost += t * d[T];
		for(int i = T; i != S; i = e[pre[i]^1]) {
			f[pre[i]] -= t;
			f[pre[i] ^ 1] += t;
		}
	}
}

int n, m;
string name[N];
map<string, int> mp;
vector<int> ans;
bool vis[N];
void dfs(int u) {
	ans.push_back(u - n);
	vis[u - n] = true;
	if(u == n + n) return ;
	for(int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];
		if(f[i ^ 1] && !vis[v]) {
			dfs(v + n);
			break;
		}
	}
}
void solve() {
	memset(h, -1, sizeof h);
	cin >> n >> m;
	S = 0, T = n + n + 1;
	add(S, 1, 2, 0);
	add(n + n, T, 2, 0);
	for(int i = 1; i <= n; i ++) {
		cin >> name[i];
		mp[name[i]] = i;
		if(i != 1 && i != n) add(i, i + n, 1, -1);
		else add(i, i + n, 2, -1);
	}
	string s, t;
	int u, v;
	for(int i = 1; i <= m; i ++) {
		cin >> s >> t;
		u = mp[s], v = mp[t];
		add(u + n, v, 1, 0);
	}
	int flow, cost;
	EK(flow, cost);
	if(flow == 0) {
		cout << "No Solution!\n";
		return ;
	}
	cout << -cost-2*(flow-1) << endl;
   //就是说没有flow=1时输出NoSoultion的数据，只有一个很特殊的可以正常输出的a -> c -> a的数据。
	dfs(1 + n);
	for(int i = 0; i < ans.size(); i ++)
		cout << name[ans[i]] << endl;
	ans.clear();
	dfs(1 + n);
	for(int i = ans.size() - 1; i >= 0; i --)
		cout << name[ans[i]] << endl;
}

int main() {
	//ios::sync_with_stdio(false);
	//cin.tie(nullptr), cout.tie(nullptr);
	int t = 1;
	//cin >> t;
	while(t --) solve();
	
	return 0;
}