个人习惯将思路注释写在代码末尾了

#include <bits/stdc++.h>

#define F(i, a, b) for(int i = (a); i <= (b); ++i)
#define dF(i, a, b) for(int i = (a); i >= (b); --i)

using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef unsigned int uint;
const int N = 1e5 + 5;
const int inf = 1e9;

int n, m, S, T, ans; string s[N]; map<string, int> mp;

int tot = 1, head[N], now[N]; LL dis[N]; bool vis[N];
struct edge { int nxt, v, w; LL c; } e[N];
void Add(int u, int v, int w, LL c) { e[++tot] = {head[u], v, w, c}, head[u] = tot; }
void Addedge(int u, int v, int w, LL c) { Add(u, v, w, c), Add(v, u, 0, -c); }
bool Spfa() {
    F(i, 1, T) dis[i] = inf; dis[S] = 0; queue<int> q; q.push(S);
    while (!q.empty()) { int u = q.front(); q.pop(), vis[u] = 0;
        for (int i = now[u] = head[u]; i; i = e[i].nxt)
            if (e[i].w && dis[u] + e[i].c < dis[e[i].v]) {
                dis[e[i].v] = dis[u] + e[i].c;
                if (!vis[e[i].v]) q.push(e[i].v), vis[e[i].v] = 1;
            }
    } return dis[T] < inf;
} int Dfs(int u, int sum) {
    if (u == T) return sum; int res = 0, r; vis[u] = 1;
    for (int i = now[u]; i && sum; i = e[i].nxt) { now[u] = i;
        if (e[i].w && !vis[e[i].v] && dis[u] + e[i].c == dis[e[i].v])
            r = Dfs(e[i].v, min(sum, e[i].w)),
            e[i].w -= r, e[i ^ 1].w += r,
            sum -= r, res += r, ans += r * e[i].c;
    } return vis[u] = 0, res;
} int Dinic() { int res = 0; while (Spfa()) res += Dfs(S, inf); return res; }

void Solve(int u, bool tp) {
    vis[u] = 1; if (!tp) cout << s[u] << "\n";
    for (int i = head[u + n]; i; i = e[i].nxt)
        if (e[i].v <= n && !vis[e[i].v]) { Solve(e[i].v, tp); break; }
    if (tp) cout << s[u] << "\n";
}

int main() {
    freopen("wmyr.in", "r", stdin);
    freopen("wmyr.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m, S = 2 * n + 1, T = S + 1;
    F(i, 1, n) cin >> s[i], mp[s[i]] = i;
    F(i, 1, m) {
        int u, v; string x, y; cin >> x >> y;
        u = min(mp[x], mp[y]), v = max(mp[x], mp[y]);
        Addedge(u + n, v, inf, 0);
    } F(i, 2, n - 1) Addedge(i, i + n, 1, -1);
    Addedge(1, 1 + n, 2, -1), Addedge(n, n + n, 2, -1);
    Addedge(S, 1, 2, 0), Addedge(n + n, T, 2, 0);
    if (Dinic() == 2) {
        cout << -ans - 2 << "\n";
        F(u, 1, n) for (int i = head[u]; i; i = e[i].nxt)
            if (e[i].v == u + n && e[i].w) vis[u] = 1;
        Solve(1, 0), Solve(1, 1);
    } else cout << "No Solution!\n";
    return 0;
}

/*
最大费用最大流
转化题意：DAG 上找到两条除 1 和 n 之外不相交的路径最大化长度和
不能重复经过点，套路性地将每个点拆成入点和出点
入点向出点连边，若为 1 和 n 点流量 2，否则流量 1，费用 1（1 和 n 选两次，其余一次，造成 1 的贡献）
原图中的 (u, v) 边，u 的出点向 c 的入点连边，流量 inf，费用 0（理论上一条边可以经过多次，不造成贡献）
源点向 1 的入点连边，n 的出点向汇点连边，流量 2，费用 0（1 和 n 选且必选两次）
跑最大费用最大流，最大流为 2 则存在，费用 - 2 是最大长度，然后取出流满的点两遍 dfs 即可
*/