#include <bits/stdc++.h>
#include <fstream>
#define int long long
#define TASK "vmst"
using namespace std;
const int MAXN = 1e3 + 7,
MAXM = 15e2 + 7;
int N, M;
struct Edge {
int u, v, c;
} E[MAXM];
bool cmp(Edge a, Edge b) {
return a.c < b.c;
}
struct DisjointSets {
int par[MAXN];
void INIT() {
for (int i = 0; i < MAXN; ++i) {
par[i] = -1;
}
}
int FIND(int v) {
return (par[v] < 0) ? (v) : (par[v] = FIND(par[v]));
}
void MERGE(int u, int v) {
u = FIND(u);
v = FIND(v);
if (u == v) {
return;
}
if (u > v) {
swap(u, v);
}
par[u] += par[v];
par[v] = u;
}
} DS;
int ANS = 0;
void SOLVE(int id) {
sort(E + 1, E + M + 1, cmp);
DS.INIT();
for (int i = 1; i <= M; ++i) {
if (DS.FIND(E[i].u) == DS.FIND(E[i].v)) {
continue;
}
cout << E[i].u << ' ' << E[i].v << '\n';
DS.MERGE(E[i].u, E[i].v);
E[i].c += 2 - id;
}
}
main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
#endif
cin >> N >> M;
for (int i = 1; i <= M; ++i) {
cin >> E[i].u >> E[i].v;
}
cout << 3 << '\n';
for (int i = 0; i < 3; ++i) {
SOLVE(i);
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlIDxmc3RyZWFtPgoKI2RlZmluZSBpbnQgbG9uZyBsb25nCgojZGVmaW5lIFRBU0sgInZtc3QiCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IE1BWE4gPSAxZTMgKyA3LAogICAgICAgICAgTUFYTSA9IDE1ZTIgKyA3OwoKaW50IE4sIE07CnN0cnVjdCBFZGdlIHsKICAgIGludCB1LCB2LCBjOwp9IEVbTUFYTV07Cgpib29sIGNtcChFZGdlIGEsIEVkZ2UgYikgewogICAgcmV0dXJuIGEuYyA8IGIuYzsKfQoKc3RydWN0IERpc2pvaW50U2V0cyB7CiAgICBpbnQgcGFyW01BWE5dOwoKICAgIHZvaWQgSU5JVCgpIHsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IE1BWE47ICsraSkgewogICAgICAgICAgICBwYXJbaV0gPSAtMTsKICAgICAgICB9CiAgICB9CgogICAgaW50IEZJTkQoaW50IHYpIHsKICAgICAgICByZXR1cm4gKHBhclt2XSA8IDApID8gKHYpIDogKHBhclt2XSA9IEZJTkQocGFyW3ZdKSk7CiAgICB9CgogICAgdm9pZCBNRVJHRShpbnQgdSwgaW50IHYpIHsKICAgICAgICB1ID0gRklORCh1KTsKICAgICAgICB2ID0gRklORCh2KTsKCiAgICAgICAgaWYgKHUgPT0gdikgewogICAgICAgICAgICByZXR1cm47CiAgICAgICAgfQoKICAgICAgICBpZiAodSA+IHYpIHsKICAgICAgICAgICAgc3dhcCh1LCB2KTsKICAgICAgICB9CgogICAgICAgIHBhclt1XSArPSBwYXJbdl07CiAgICAgICAgcGFyW3ZdID0gdTsKICAgIH0KfSBEUzsKCmludCBBTlMgPSAwOwoKdm9pZCBTT0xWRShpbnQgaWQpIHsKICAgIHNvcnQoRSArIDEsIEUgKyBNICsgMSwgY21wKTsKICAgIERTLklOSVQoKTsKCiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBNOyArK2kpIHsKICAgICAgICBpZiAoRFMuRklORChFW2ldLnUpID09IERTLkZJTkQoRVtpXS52KSkgewogICAgICAgICAgICBjb250aW51ZTsKICAgICAgICB9CgogICAgICAgIGNvdXQgPDwgRVtpXS51IDw8ICcgJyA8PCBFW2ldLnYgPDwgJ1xuJzsKCiAgICAgICAgRFMuTUVSR0UoRVtpXS51LCBFW2ldLnYpOwoKICAgICAgICBFW2ldLmMgKz0gMiAtIGlkOwogICAgfQp9CgptYWluKCkgewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTsKICAgIGNpbi50aWUoTlVMTCk7CiAgICBjb3V0LnRpZShOVUxMKTsKCiNpZm5kZWYgT05MSU5FX0pVREdFCglmcmVvcGVuKFRBU0siLmlucCIsICJyIiwgc3RkaW4pOwoJZnJlb3BlbihUQVNLIi5vdXQiLCAidyIsIHN0ZG91dCk7CiNlbmRpZgoKICAgIGNpbiA+PiBOID4+IE07CiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBNOyArK2kpIHsKICAgICAgICBjaW4gPj4gRVtpXS51ID4+IEVbaV0udjsKICAgIH0KCiAgICBjb3V0IDw8IDMgPDwgJ1xuJzsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgMzsgKytpKSB7CiAgICAgICAgU09MVkUoaSk7CiAgICB9Cgp9Cg==