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

#define int long long

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,M;
	cin>>N>>M;
	if(N>1500)exit(1);
	vector<vector<int>>g(N+1);
	vector<pair<int,int>>e;
	for(int i=0;i<M;i++){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
		e.emplace_back(a,b);
	}
	vector<pair<int,int>>ans(N*2);
	for(auto[a,b]:e){
		vector<int>v(N+1,-1);
		vector<vector<pair<int,int>>>w(2);
		auto dfs=[&](auto self,int i)->void{
			for(int j:g[i]){
				if(v[j]!=-1){
					continue;
				}
				v[j]=v[i];
				self(self,j);
				w[v[i]].emplace_back(i,j);
			}
		};
		v[a]=0;
		v[b]=1;
		int aaa=-1,bbb=-1;
		for(int aa:g[a]){
			for(int bb:g[b]){
				if(aa==b||bb==a){
					continue;
				}
				int ok=0;
				for(int i:g[aa]){
					if(i==bb){
						ok=1;
					}
				}
				if(ok){
					aaa=aa;
					bbb=bb;
				}
			}
		}
		if(aaa!=-1){
			v[aaa]=0;
			v[bbb]=1;
			dfs(dfs,aaa);
			dfs(dfs,bbb);
			if(count(v.begin(),v.end(),-1)>1){
				continue;
			}
			vector<pair<int,int>>s;
			for(auto[a,b]:w[0]){
				s.emplace_back(a,b);
			}
			for(auto[a,b]:w[1]){
				s.emplace_back(a,b);
			}
			s.emplace_back(a,aaa);
			s.emplace_back(b,bbb);
			s.emplace_back(a,b);
			s.emplace_back(aaa,bbb);
			reverse(w[0].begin(),w[0].end());
			reverse(w[1].begin(),w[1].end());
			for(auto[a,b]:w[0]){
				s.emplace_back(a,b);
			}
			for(auto[a,b]:w[1]){
				s.emplace_back(a,b);
			}
			vector<bitset<1501>>v(N+1);
			for(int i=1;i<=N;i++)v[i][i]=1;
			for(auto[a,b]:s){
				v[a]=v[b]=v[a]|v[b];
			}
			int k=1;
			while(k<=N&&v[k].count()==N)k++;
			if(k<=N){
				exit(1);
			}
			else if(s.size()<ans.size()){
				ans=s;
			}
		}
		fill(v.begin(),v.end(),-1);
		w[0].clear();
		w[1].clear();
		v[a]=0;
		v[b]=1;
		dfs(dfs,a);
		dfs(dfs,b);
		vector<pair<int,int>>s;
		for(auto[a,b]:w[0]){
			s.emplace_back(a,b);
		}
		for(auto[a,b]:w[1]){
			s.emplace_back(a,b);
		}
		s.emplace_back(a,b);
		reverse(w[0].begin(),w[0].end());
		reverse(w[1].begin(),w[1].end());
		for(auto[a,b]:w[0]){
			s.emplace_back(a,b);
		}
		for(auto[a,b]:w[1]){
			s.emplace_back(a,b);
		}
		if(s.size()<ans.size()){
			ans=s;
		}
	}
	cout<<ans.size()<<'\n';
	for(auto[a,b]:ans){
		cout<<a<<' '<<b<<'\n';
	}
	return 0;
}