#include <cassert>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
int const MAX_N = 1e5;
void dassert(bool const statement) {
#ifdef _DEBUG
assert(statement);
#endif
}
// 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]);
}
// This probably breaks the time-complexity.
void reroot(int const x) {
int const r = find(x);
parent[r] = x;
parent[x] = 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 dsu::find(v);
v = p;
}
}
void reroot(int v) {
int const fv = dsu::find(v);
int const p = parent[fv];
dassert(v != -1 && fv != -1);
dassert(v != p && fv != p);
if (p == -1) {
sz[v] = sz[fv];
dsu::reroot(v);
return;
}
reroot(p);
sz[v] = sz[p];
sz[p] -= sz[fv];
#ifdef _DEBUG
dassert(sz[v] > sz[p]);
#endif
parent[fv] = -1;
dsu::reroot(v);
parent[p] = fv;
dassert(parent[v] == -1 && parent[fv] == -1 && parent[p] != 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);
dassert(u != v);
parent[v] = u;
do {
u = dsu::find(u);
sz[u] += sz[v];
u = parent[u];
} while (u != -1);
}
else {
int cu = dsu::find(u);
int cv = dsu::find(v);
while (cu != cv) {
dassert(cu != -1 && cv != -1);
int& c = sz[cu] < sz[cv] ? cu : cv;
int& pc = parent[c];
dassert(pc != -1 && pc != c);
dsu::parent[c] = pc;
c = dsu::find(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);
}
#ifdef _DEBUG
cout << "\n";
#endif
for (int i = 0; i < n; i++)
if (parent[i] != -1)
cout << i + 1 << " " << parent[i] + 1 << "\n";
}
