#include <cassert>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
int const MAX_N = 1e5;
// 2 * MAX_N * 4 B = 0.8 MB
namespace dsu {
int parent[MAX_N];
void init() {
iota(parent, parent + MAX_N, 0);
}
int find(int const x) {
if (parent[x] == x)
return x;
return parent[x] = find(parent[x]);
}
}
// -1 if none
int parent[MAX_N];
int sz[MAX_N];
int& up(int const v) {
return parent[dsu::find(v)];
}
int root(int v) {
while (true) {
int const p = up(v);
if (p == -1)
return v;
v = p;
}
}
void reroot(int v) {
while (parent[v] != -1) {
int const p = parent[v];
sz[p] -= sz[v];
swap(parent[v], parent[p]);
sz[v] += sz[p];
}
}
void add_edge(int u, int v) {
int ru = root(u);
int rv = root(v);
if (ru != rv) {
if (sz[ru] < sz[rv]) {
swap(u, v);
swap(ru, rv);
}
reroot(v);
parent[v] = u;
do {
sz[u] += sz[v];
u = up(u);
} while (u != -1);
}
else {
int cu = u;
int cv = v;
while (cu != cv) {
#ifdef _DEBUG
assert(cu != -1 && cv != -1);
#endif
int& c = sz[cu] < sz[cv] ? cu : cv;
int& pc = up(c);
dsu::parent[dsu::find(c)] = pc;
c = pc;
pc = -1;
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
dsu::init();
fill(sz, sz + MAX_N, 1);
fill(parent, parent + MAX_N, -1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--; v--;
add_edge(u, v);
}
for (int i = 0; i < n; i++)
if (parent[i] != -1)
cout << i + 1 << " " << parent[i] + 1 << "\n";
}
