#include <bits/stdc++.h>
using namespace std;
 
int main() {
	map<string, int> dict;
	vector<string> rdict;
	int N, M;
	cin >> N >> M;
	for(int i = 0; i < M; i++) {
		string parent, child;
		int pi, ci;
		cin >> parent >> child;
		if(dict.find(parent) != dict.end())
			pi = dict[parent];
		else {
			pi = dict[parent] = rdict.size();
			rdict.push_back(parent);
		}
		if(dict.find(child) != dict.end())
			ci = dict[child];
		else {
			ci = dict[child] = rdict.size();
			rdict.push_back(child);
		}
	}
	for(map<string, int>::iterator it = dict.begin(); it != dict.end(); it++)
		cout << it->first << " " << it->second << endl;
	for(int i = 0; i < rdict.size(); i++)
		cout << i << " " << rdict[i] << endl;
	return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpIHsKCW1hcDxzdHJpbmcsIGludD4gZGljdDsKCXZlY3RvcjxzdHJpbmc+IHJkaWN0OwoJaW50IE4sIE07CgljaW4gPj4gTiA+PiBNOwoJZm9yKGludCBpID0gMDsgaSA8IE07IGkrKykgewoJCXN0cmluZyBwYXJlbnQsIGNoaWxkOwoJCWludCBwaSwgY2k7CgkJY2luID4+IHBhcmVudCA+PiBjaGlsZDsKCQlpZihkaWN0LmZpbmQocGFyZW50KSAhPSBkaWN0LmVuZCgpKQoJCQlwaSA9IGRpY3RbcGFyZW50XTsKCQllbHNlIHsKCQkJcGkgPSBkaWN0W3BhcmVudF0gPSByZGljdC5zaXplKCk7CgkJCXJkaWN0LnB1c2hfYmFjayhwYXJlbnQpOwoJCX0KCQlpZihkaWN0LmZpbmQoY2hpbGQpICE9IGRpY3QuZW5kKCkpCgkJCWNpID0gZGljdFtjaGlsZF07CgkJZWxzZSB7CgkJCWNpID0gZGljdFtjaGlsZF0gPSByZGljdC5zaXplKCk7CgkJCXJkaWN0LnB1c2hfYmFjayhjaGlsZCk7CgkJfQoJfQoJZm9yKG1hcDxzdHJpbmcsIGludD46Oml0ZXJhdG9yIGl0ID0gZGljdC5iZWdpbigpOyBpdCAhPSBkaWN0LmVuZCgpOyBpdCsrKQoJCWNvdXQgPDwgaXQtPmZpcnN0IDw8ICIgIiA8PCBpdC0+c2Vjb25kIDw8IGVuZGw7Cglmb3IoaW50IGkgPSAwOyBpIDwgcmRpY3Quc2l6ZSgpOyBpKyspCgkJY291dCA8PCBpIDw8ICIgIiA8PCByZGljdFtpXSA8PCBlbmRsOwoJcmV0dXJuIDA7Cn0=

OSA4CmthbG9iYXRpcHB1cyBhcmNoZW9oaXBwdXMKa2Fsb2JhdGlwcHVzIHBhcmFoaXBwdXMKcGFyYWhpcHB1cyBtZXJ5Y2hpcHB1cwptZXJ5Y2hpcHB1cyBkaW5vaGlwcHVzCm1lcnljaGlwcHVzIGNhbGlwcHVzCm1lcnljaGlwcHVzIGNvcm1vaGlwcGFyaW9uCmRpbm9oaXBwdXMgaGlwcGlkaW9uCmRpbm9oaXBwdXMgZXF1dXMKa2Fsb2JhdGlwcHVzIGVxdXVz

9 8
kalobatippus archeohippus
kalobatippus parahippus
parahippus merychippus
merychippus dinohippus
merychippus calippus
merychippus cormohipparion
dinohippus hippidion
dinohippus equus
kalobatippus equus