public void solve() throws IOException {
    int n = nextInt();
    int m = nextInt();
    
    Map<String, String> wordMap = new HashMap<String, String>();
    
    for (int x = 0; x < m; x++) {
      String first = nextToken();
      String second = nextToken();
      if (second.length() < first.length()) {
        wordMap.put(first, second);
      }
    }
    
    StringBuffer output = new StringBuffer();
    
    for (int x = 0; x < n; x++) {
      String word = nextToken();
      if (x != 0) {
        output.append(" ");
      }
      if (wordMap.containsKey(word)) {
        output.append(wordMap.get(word));
      } else {
        output.append(word);
      }
    }
    
    System.out.println(output.toString());
  }