/// Mesaj4
/// Toate mesajele stranse in nodul de gard maxim cu n-1 pasi
/// Distribuirea lor la restul de noduri prin n-1 pasi
#include <bits/stdc++.h>
using namespace std;
ifstream in("mesaj4.in");
ofstream out("mesaj4.out");
#define NMAX 100000
vector <int> G[NMAX+5];
int N, M, Use[NMAX+5], Grad[NMAX+5], Max;

void Read () {
    in >> N >> M;
    int x, y;
    for (int i = 0; i < M; i++) {
        in >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
        Grad[x]++;Grad[y]++;
    }
    for (int i = 1; i <= N; i++)
        if (Grad[i] > Max)
            Max = Grad[i];
}

void DFS1 (int Node) {
    Use[Node] = 1;

    for (int i = 0; i < G[Node].size(); i++) {
        int Vecin = G[Node][i];
        if (!Use[Vecin] && (Grad[Vecin] != Max || Grad[Node] != Max)) {
            DFS1(Vecin);
            out << Vecin << " " << Node << '\n';
        }
    }
}

void DFS2 (int Node) {
    Use[Node] = 1;

    for (int i = 0; i < G[Node].size(); i++) {
        int Vecin = G[Node][i];
        if (!Use[Vecin]) {
            out << Node << " " << Vecin << '\n';
            DFS2(Vecin);
        }
    }
}


int main () {
    Read();
    out << 2 * N - 2 << '\n';
    for (int i = 1; i <= N; i++)
        if (Grad[i] = Max)
            DFS1(i);
    for (int i = 1; i <= N; i++)
        Use[i] = 0;
    for (int i = 1; i <= N; i++)
        if (Grad[i] = Max)
            DFS2(i);
}