#include <bits/stdc++.h>
using namespace std;
const long long int maxn = 1e5;
int main() {
  int n, k;
  cin >> n >> k;
  unordered_map<string, string> m;
  while (k--) {
    string a, b;
    cin >> a >> b;
    if (a.size() <= b.size()) {
      m[a] = a;
      m[b] = a;
    } else if (a.size() > b.size()) {
      m[a] = b;
      m[b] = b;
    }
  }
  while (n--) {
    string a;
    cin >> a;
    cout << m[a] << " ";
  }
  return 0;
}
