#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int long long
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define pb push_back
const int MAXN=1e2+10;
typedef pair<int,int> pii;
int n,m,dp[MAXN][MAXN];
vector<vector<int>> ans;
vector<int> g[MAXN],g1[MAXN];
bool mark[MAXN],used[MAXN];
void show(vector<int> a){
for(auto x:a) cout<<x<<" ";
cout<<"\n";
}
vector<int> get(vector<int> lista){
vector<int> cor(n); iota(all(cor),0);
int a=lista[0];
for(auto u:lista) cor[u]=a;
return cor;
}
void dfs1(int x){
mark[x]=1;
for(auto u:g1[x]){
if(mark[u]) continue;
g[u].pb(x),g[x].pb(u);
dfs1(u);
}
}
void bfs(int x){
fall(i,0,n) dp[x][i]=1000;
dp[x][x]=0;
queue<int> fila;
fila.push(x);
while(!fila.empty()){
auto a=fila.front(); fila.pop();
for(auto u:g[a]){
if(dp[x][u]==1000){
dp[x][u]=dp[x][a]+1;
fila.push(u);
}
}
}
}
void dfs(int x){
mark[x]=1;
for(auto u:g[x]){
if(mark[u] || used[u]) continue;
ans.pb(get({u,x}));
dfs(u);
ans.pb(get({u,x}));
}
}
int32_t main(){
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
fall(i,1,m){
int a,b; cin>>a>>b;
g1[a].pb(b),g1[b].pb(a);
}
dfs1(0);
vector<vector<int>> real_ans;
fall(root,0,n-1){
ans.clear();
bfs(root);
int mn=0;
fall(i,0,n-1) mn=max(mn,dp[root][i]);
fall(i,0,mn){
fall(j,0,n-1) mark[j]=0;
dfs(root);
fall(j,0,mn-i-1){
vector<int> lista;
fall(k,0,n-1) if(dp[root][k]==j || dp[root][k]==j+1) lista.pb(k);
ans.pb(get(lista));
}
fall(j,0,n-1) if(dp[root][j]==mn-i) used[j]=1;
}
if(sz(real_ans)==0 || sz(ans)<sz(real_ans)) real_ans=ans;
}
cout<<sz(real_ans)<<"\n";
for(auto ar:real_ans) show(ar);
}
