#include <bits/stdc++.h>
using namespace std;
struct Data {
  char c;
  int end;
  int next[26];
  Data() {
    end = -1;
    for (int i = 0; i < 26; i++) next[i] = 0;
  }
};
vector<Data> bor;
void add(string s, int pos) {
  int id = 0;
  for (int i = 0; i < s.size(); i++) {
    char c = s[i];
    if (bor[id].next[c - 'a'] != 0)
      id = bor[id].next[c - 'a'];
    else {
      Data d;
      d.c = c;
      bor[id].next[c - 'a'] = bor.size();
      id = bor.size();
      bor.push_back(d);
    }
  }
  bor[id].end = pos;
}
int find(string s) {
  int id = 0;
  for (int i = 0; i < s.size(); i++) {
    char c = s[i];
    if (bor[id].next[c - 'a'] != 0)
      id = bor[id].next[c - 'a'];
    else
      return -1;
  }
  return bor[id].end;
}
int main() {
  int n, m;
  cin >> n >> m;
  Data d;
  d.c = '$';
  bor.push_back(d);
  vector<string> a;
  for (int i = 0; i < m; i++) {
    string s1, s2;
    cin >> s1 >> s2;
    add(s1, a.size());
    a.push_back(s2);
    add(s2, a.size());
    a.push_back(s1);
  }
  for (int i = 0; i < n; i++) {
    string s1;
    cin >> s1;
    int f = find(s1);
    string s2 = a[f];
    if (s1.size() < s2.size())
      cout << s1 << " ";
    else if (s1.size() > s2.size())
      cout << s2 << " ";
    else if (find(s1) > find(s2))
      cout << s2 << " ";
    else
      cout << s1 << " ";
  }
  cout << endl;
  return 0;
}
