/* Input format

  3 3
  a b c
  a b
  b c
  c a

*/
#include<bits/stdc++.h>

using namespace std;

int main() {
  int node, edge;
  cin >> node >> edge;
  map<string, int>mp;
  map<int, string>revMp;
  for(int i = 0; i < node; i++) {
    string in;
    cin >> in;
    mp[in] = i;
    revMp[i] = in;
  }
/**
  * converting string to number
  */
  for(int i = 0; i < edge; i++) {
    string a, b;
    cin >> a >> b;
    cout << mp[a] << ' ' << mp[b] << endl;
  }
/**
  * converting number to string
  */
  for(int i = 0; i < node; i++) cout << revMp[i] << ' ';
  cout << endl;
}