#include<cstdio>
#include<vector>

using namespace std;

#define MAXN 1000000
#define MAXM 10000000

vector<int> byfirst[MAXN];
vector<int> bysecond[MAXN];
pair<int,int> input[MAXM];
int n, m;

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		// Budeme pro jednoduchost předpokládat indexování jeskyň od 0 do n-1.
		scanf("%d%d", &input[i].first, &input[i].second);
		if (input[i].first > input[i].second) // Menší jeskyně vždy do první složky
			swap(input[i].first, input[i].second);
	}

	// Roztřídění podle druhé složky
	for (int i = 0; i < m; i++) {
		bysecond[input[i].second].push_back(input[i].first);
	}

	// Roztřídění podle první složky
	for (int i = 0; i < n; i++) {
		for (unsigned int j = 0; j < bysecond[i].size(); j++) {
			byfirst[bysecond[i][j]].push_back(i);
		}
	}

	int lastx = -1, lasty = -1;
	for (int i = 0; i < n; i++) {
		for (unsigned int j = 0; j < byfirst[i].size(); j++) {
			if (i != lastx || lasty != byfirst[i][j]) {
				printf("%d %d\n", i, byfirst[i][j]);
				lastx = i;
				lasty = byfirst[i][j];
			}
		}
	}
	return 0;
}