#include <iostream> #include <list> #include <string> #include <unordered_map> using namespace std; int main() { int n, m; cin >> n >> m; list<string> queue; unordered_map<string, list<string>::iterator> pos; string name, x, y; for (int i = 0; i < n; ++i) { cin >> name; queue.push_back(name); pos[name] = prev(queue.end()); } for (int i = 0; i < m; ++i) { cin >> x >> y; auto it_x = pos[x]; auto it_y = pos[y]; if (it_x != it_y) { queue.erase(it_x); pos[x] = queue.insert(it_y, x); } } for (const string& name : queue) { cout << name << " "; } return 0; }