https://codeforces.com/problemset/problem/499/B

#include<bits/stdc++.h>
using namespace std;
map<string,string>mp;
int main(void)
{
	int n,m; cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		string a,b; cin>>a>>b;
		if(a.size()<=b.size()) mp[a]=a,mp[b]=a;
		else mp[a]=b,mp[b]=b;
	}
	string s; 
	getline(cin,s);
	getline(cin,s);
	stringstream l(s);
	while(l>>s) cout<<mp[s]<<" ";
	return 0;
}