#include<bits/stdc++.h>
using namespace std;

#define endl        "\n"
#define LL          long long
#define READ(x)     freopen(x,"r",stdin)
#define WRITE(x)    freopen(x,"w",stdout)
#define BOOST       ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pb          push_back
#define mem(x,y)    memset(x,y,sizeof x )
#define ch          printf("Came Here!!!!!!!!!!!!!!!\n")
#define deb(x)      cerr<<#x<<" :: "<<x<<" "
#define dnl         cerr<<endl
#define FOR(i,n)    for(int i=0;i<n;i++)
#define cnd         tree[idx]
#define lc          tree[idx*2]
#define rc          tree[idx*2+1]
#define lnd         (2*idx),(b),( (b+e) /2 )
#define rnd         ((2*idx)+1),(((b+e)/2)+1),(e)
#define popcount    __builtin_popcount

const LL        INF = 1LL<<60;
const double    PI = 2.0 * acos(0.0);

typedef pair<int,int>   pii;
typedef pair<LL,LL>     pll;
typedef vector<int>     vi;
typedef vector<LL>      vl;
typedef vector<pii>     vii;
typedef vector<pll>     vll;

//// Including Policy Based DS
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
/////cout<<*X.find_by_order(1)<<endl;
/////cout<<X.order_of_key(-5)<<endl;
//typedef tree<
//int,
//null_type,
//less<int>,
//rb_tree_tag,
//tree_order_statistics_node_update>
//ordered_set;

// Grid direction array [4]
int X[4]={0,0,-1,1};
int Y[4]={1,-1,0,0};
// Grid direction array [8]
int X8[8]={0,0,1,-1,-1,1,1,-1};
int Y8[8]={1,-1,0,0,-1,-1,1,1};
// Bishop direction array
int BX[8]={0,0,1,-1,-1,1,1,-1};
int BY[8]={1,-1,0,0,-1,-1,1,1};
// Knight Direction Array
int KX[8] = {1,1,2,2,-1,-1,-2,-2};
int KY[8] = {2,-2,1,-1,2,-2,1,-1};

inline LL modMul(LL a, LL b,LL mod){
    LL ans = 0;
    a = a % mod;
    while (b > 0){
        if ( b % 2 )ans = (ans%mod+ a%mod) % mod;
        a = (a%mod * 2%mod) % mod;
        b /= 2;
    }
    return ans % mod;
}
inline LL power(LL a,LL b,LL mod){
    if(b==0)return 1LL%mod;
    LL x=power( a,b/2,mod );
    x = (x*x) % mod;
    if( b%2==1 )x = (x*a)%mod;
    return x%mod;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//-------------------------------------------------------------------------------
//-------------------------------------------------------------------------------
const int mx = 2e4+10;

int deg[mx];

struct DSU{
    int par[mx];
    int sz[mx];
    void init(int n){FOR(i,n)par[i]=i,sz[i]=1;}
    int f(int u){
        return (par[u]==u)?u:par[u]=f(par[u]);
    }
    void mer(int u,int v){
        u=f(u),v=f(v);
        if(u!=v){
            par[v]=u;
            sz[u]+=sz[v];
        }
    }

    bool single(int u){
        return sz[f(u)]==1;
    }
} dsu;
void solve(int cs){
    int n,k,m;
    cin>>n>>m;
    while(m--){
        int u,v;cin>>u>>v;deg[u]++;deg[v]++;
    }
    vector<int>nodes;
    FOR(i,n)nodes.pb(i);
    sort(nodes.begin(),nodes.end(),[&](int a,int b){
        return deg[a]<deg[b];
    });
    vii E;
    dsu.init(n);
    for(int i=0;i<n;i++){
        int u = nodes[i];
        int x = deg[u];
        for(int j=i+1;j<n;j++){
            if(deg[u]<1)break;
            int v = nodes[j];
            if(deg[v]>1 and dsu.f(u)!=dsu.f(v)){
                if(deg[v]==1 and dsu.single(v) and dsu.single(u) and deg[u]==1){

                }
                else{
                    dsu.mer(u,v);
                    deg[u]--,deg[v]--;
                    E.pb({u,v});
                }
            }
        }
    }

    FOR(i,n){
        int u = nodes[i];
        if(deg[u]==1){
            for(int j=0;j<n;j++){
                int v = nodes[j];
                if(dsu.f(u)!=dsu.f(v) and deg[v]==1){
                    dsu.mer(u,v);
                    deg[u]--,deg[v]--;
                    E.pb({u,v});
                }
            }
        }
    }

    FOR(i,n){
        int u = nodes[i];
        if(deg[u]==1){
            for(int j=0;j<n;j++){
                int v = nodes[j];
                if(dsu.f(u)!=dsu.f(v) and deg[v]>0){
                    dsu.mer(u,v);
                    deg[u]--,deg[v]--;
                    E.pb({u,v});
                }
            }
        }
    }


    int cnt = 0;
    FOR(i,n)if(deg[i]==0)cnt++;

    cout<<n-cnt<<endl;
    cout<<n<<" "<<n-1<<endl;
    for(pii e:E){
        cout<<e.first<<" "<<e.second<<endl;
    }

}
int main(){
    BOOST;
//    READ("in.txt");
//    WRITE("out.txt");
    #ifdef MujahidPC
        double start = clock();
    #endif

    int t;
    t = 1;
//    cin>>t;
    FOR(cs,t)solve(cs+1);

    #ifdef MujahidPC
        double tim = (clock() - start)/CLOCKS_PER_SEC;
        cerr<<"Running Time : "<<tim<<" \n";
    #endif
    return 0;
}