#include <bits/stdc++.h>
using namespace std;
int lss(int* arr, int n) {
  int max_so_far = arr[0], curr_max = arr[0];
  for (int i = 1; i < n; i++) {
    curr_max = max(arr[i], curr_max + arr[i]);
    max_so_far = max(max_so_far, curr_max);
  }
  return max_so_far;
}
void buildTree(int* arr, int* tree, int si, int ei, int ni) {
  if (si == ei) {
    tree[ni] = arr[si];
    return;
  }
  buildTree(arr, tree, si, (si + ei) / 2, 2 * ni);
  buildTree(arr, tree, (si + ei) / 2 + 1, ei, 2 * ni + 1);
  tree[ni] = tree[2 * ni] + tree[2 * ni + 1];
}
int query(int* tree, int si, int ei, int l, int r, int ni) {
  if (l > ei || r < si) return 0;
  if (si >= l && ei <= r) return tree[ni];
  return (query(tree, si, (si + ei) / 2, l, r, 2 * ni) +
          query(tree, (si + ei) / 2 + 1, ei, l, r, 2 * ni + 1));
}
void update(int* arr, int* tree, int si, int ei, int ni, int index, int value) {
  if (si == ei) {
    arr[index] = value;
    tree[ni] = value;
    return;
  }
  int mid = (si + ei) / 2;
  if (index <= mid)
    update(arr, tree, si, mid, 2 * ni, index, value);
  else
    update(arr, tree, mid + 1, ei, 2 * ni + 1, index, value);
  tree[ni] = tree[2 * ni] + tree[2 * ni + 1];
}
int* prefix_sum(int* arr, int n) {
  int* p_sum = new int[n]();
  p_sum[0] = arr[0];
  for (int i = 1; i < n; i++) {
    p_sum[i] = (arr[i] + p_sum[i - 1]);
  }
  return p_sum;
}
int binary_search(int* arr, int si, int ei, int x) {
  if (si == ei) return si;
  int mid = (si + ei) / 2;
  if (x > arr[mid - 1] && x <= arr[mid]) return mid;
  if (x > arr[mid])
    return binary_search(arr, mid + 1, ei, x);
  else
    return binary_search(arr, si, mid, x);
}
bool comp(pair<int, int> x, pair<int, int> y) { return x.first < y.first; }
void solve() {
  int n, m;
  cin >> n >> m;
  unordered_map<string, string> map;
  for (int i = 0; i < m; i++) {
    string s1, s2;
    cin >> s1 >> s2;
    map[s1] = s2 + "2";
    map[s2] = s1 + "1";
  }
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    string x = map[s];
    string y = x;
    y.pop_back();
    if (y.length() < s.length())
      cout << y << " ";
    else if (y.length() > s.length())
      cout << s << " ";
    else {
      char hi = x[x.length() - 1];
      if (hi == '1')
        cout << y << " ";
      else
        cout << s << " ";
    }
  }
  cout << endl;
  return;
}
int main() {
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
