#include<bits/stdc++.h>
using namespace std;
int n,m;
int ez1[12],ez2[12];
int dp[2048][12];
bool mn[2048][12];
pair<int,int> hora[2048][12];
pair<int,int> kog[2048][12];
bool same(int x, int y)
{
    if (ez1[x]==ez1[y]) return true;
    if (ez2[x]==ez1[y]) return true;
    if (ez2[x]==ez2[y]) return true;
    if (ez1[x]==ez2[y]) return true;
    return false;
}
int rec(int mask, int ch)
{
    //cout<<mask<<" "<<ch<<"\n";
    if (ch==m+1)
    {
        int br=0;
        for (int q=0;q<m;q++)
        {
            if ((mask>>q)%2==1) br++;
        }
        return br;
    }
    if (mn[mask][ch]) return dp[mask][ch];
    mn[mask][ch]=1;
    if ((mask>>(ch-1))%2==0)
    {
        int ans=0;
        for (int q=ch+1;q<=m;q++)
        {
            if ((mask>>(q-1))%2==0 && same(ch,q))
            {
                //cout<<ch<<" "<<q<<" "<<(1<<(ch-1))<<" "<<(1<<(q-1))<<" "<<mask+(1<<(ch-1))+(1<<(q-1))<<"\n";
                int ch1=rec(mask+(1<<(ch-1))+(1<<(q-1)),ch+1);
                if (ch1>ans)
                {
                    ans=ch1;
                    hora[mask][ch]=make_pair(ch,q);
                    kog[mask][ch]=make_pair(mask+(1<<(ch-1))+(1<<(q-1)),ch+1);
                }
            }
        }
        int ch1=rec(mask,ch+1);
        if (ch1>ans)
        {
            ans=ch1;
            hora[mask][ch]=make_pair(0,0);
            kog[mask][ch]=make_pair(mask,ch+1);
        }
        dp[mask][ch]=ans;
        return dp[mask][ch];
    }
    else
    {

        hora[mask][ch]=make_pair(0,0);
        kog[mask][ch]=make_pair(mask,ch+1);
        dp[mask][ch]=rec(mask,ch+1);
        return dp[mask][ch];
    }
}
int main()
{
    cin>>n>>m;
    for (int q=1;q<=m;q++)
    {
        cin>>ez1[q]>>ez2[q];
    }
    if (m==1)
    {
        cout<<"0\n";
        return 0;
    }
    int ans=rec(0,1);
    ans/=2;
    cout<<ans<<"\n";
    int mask=0;
    int ch=1;
    while (ch<=m)
    {
        //cout<<mask<<" "<<ch<<"\n";
        if (hora[mask][ch].first!=0) cout<<hora[mask][ch].first<<" "<<hora[mask][ch].second<<"\n";
        int mask1=kog[mask][ch].first,ch1=kog[mask][ch].second;
        mask=mask1;
        ch=ch1;
    }
}
/*
10 10
4 9
5 6
4 6
1 4
10 1
12 5
3 1
3 9
5 2
6 8

*/
