#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m;
  cin >> n >> m;
  int i;
  map<string, string> mp1to2;
  map<string, string> mp2to1;
  map<string, int> mp1p;
  map<string, int> mp2p;
  for (i = 1; i <= m; i++) {
    string w1, w2;
    cin >> w1 >> w2;
    mp1to2[w1] = w2;
    mp2to1[w2] = w1;
    mp1p[w1]++;
    mp2p[w2]++;
  }
  for (i = 1; i <= n; i++) {
    string word;
    cin >> word;
    if (mp1p[word] > 0) {
      int len1 = word.length();
      int len2 = mp1to2[word].length();
      if (len1 <= len2) {
        printf("%s ", word.c_str());
      } else {
        printf("%s ", mp1to2[word].c_str());
      }
    } else {
      int len1 = mp2to1[word].length();
      int len2 = word.length();
      if (len1 <= len2) {
        printf("%s ", mp2to1[word].c_str());
      } else {
        printf("%s ", word.c_str());
      }
    }
  }
}
