#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;
}