#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e3 + 10;
int n, m;
string x1[maxn], x2[maxn], ans[maxn];
map<string, int> loc;
int main(int argc, char const *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  while (cin >> n >> m) {
    loc.clear();
    for (int i = 1; i <= m; i++) {
      cin >> x1[i] >> x2[i];
      loc[x1[i]] = loc[x2[i]] = i;
      if (x1[i].size() > x2[i].size()) {
        ans[i] = x2[i];
      } else
        ans[i] = x1[i];
    }
    while (n--) {
      cin >> x1[0];
      cout << ans[loc[x1[0]]] << ' ';
    }
    cout << endl;
  }
  return 0;
}
