解法一：链表+Map

用 Map 存储结点，进一步构造结点链表，找出有两个前序的结点即为公共后缀的起点。
注意考虑两个字符串的头结点一致的边界情况。

#include <bits/stdc++.h>
using namespace std;
class Node {
public:
    string address;
    char data;
    string next_address;
    Node *next;
    Node *pre;
    Node(string address, char data, string next_address) : address(address),
                                                           data(data),
                                                           next_address(next_address),
                                                           pre(nullptr) {}
};
map<string, Node> nodeMap;
int main() {
    string first, last;
    int N;
    cin >> first >> last >> N;
    string address, next;
    char data;
    for (int i = 0; i < N; ++i) {
        cin >> address >> data >> next;
        nodeMap.emplace(address, Node(address, data, next));
    }
    if (first==last) {
        cout << first << '\n';
        return 0;
    }
    for (auto &it:nodeMap) {
        auto nextPair = nodeMap.find(it.second.next_address);
        if (nextPair != nodeMap.end()) {
            it.second.next = &nextPair->second;
            if (nextPair->second.pre == nullptr) {
                nextPair->second.pre = &it.second;
            } else {
                cout << nextPair->second.address << '\n';
                return 0;
            }
        } else {
            it.second.next = nullptr;
        }
    }
    cout << "-1\n";
}