//EGOI 2024 Make them Meet
//https://qoj.ac/contest/1765/problem/9189
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
const ll MAXN = 105;
vll g[MAXN], h(MAXN), P(MAXN,-1), child(MAXN,0); vector<bool> vis(MAXN,false);
void dfs(ll v){
vis[v]=true;
for(auto u:g[v]) if(!vis[u]) h[u]=h[v]+1, P[u]=v, dfs(u);
}
void SolveLine(ll n,ll root){
cout << 2*n << "\n";
for(int i=0; i<2*n; i++){
for(int v=0; v<n; v++){
ll ans=root;
if(h[v]%2==i%2) ans=v;
else if(P[v]!=-1) ans=P[v];
cout << ans << " ";
}
cout << "\n";
}
}
int main(){
ll n, m, a, b;
cin >> n >> m;
for(int i=0; i<m; i++){
cin >> a >> b;
g[a].push_back(b); g[b].push_back(a);
}
h[0]=0; dfs(0); ll root=max_element(h.begin(),h.end())-h.begin();
fill(vis.begin(),vis.end(),false); fill(P.begin(),P.end(),-1);
h[root]=0; dfs(root); ll x=root; vector<bool> vis2(n,false);
if(*max_element(h.begin(),h.end())==n-1){SolveLine(n,root); return 0;}
for(int i=0; i<n; i++) if(P[i]!=-1) child[P[i]]++;
for(int i=0; i<n; i++) if(h[i]>h[x] && child[i]>1) x=i;
for(auto u:g[P[x]]) vis2[u]=true;
ll y=-1, cur; vll path;
for(int i=0; i<n; i++) if(P[i]==x && (y==-1 || !vis2[i])) y=i, cur=y;
while(true){
ll temp=-1;
for(auto v:g[cur]) if(P[v]==cur){temp=v; break;}
if(temp==-1) break;
cur=temp; path.push_back(cur);
}
fill(vis.begin(),vis.end(),false); swap(g[y][0],*find(g[y].begin(),g[y].end(),x));
for(auto v:path) vis[v]=true;
sort(g[x].begin(),g[x].end(),[&](ll v,ll u){
if((P[v]==x)!=(P[u]==x)) return (P[v]==x)>(P[u]==x);
return v<u;
});
fill(P.begin(),P.end(),-1); h[y]=0; dfs(y);
for(int i=0; i<(ll)path.size(); i++) h[path[i]]=i+1, P[path[i]]=(i?path[i-1]:y);
int child1 ;
if(path.empty()) child1 = -1 ;
else child1 = path[0] ;
cout << 6*n << "\n"; ll ans;
for(int i=1 ; i<=4*n ; i++){
for(int j=0 ; j<n ; j++){
if(j==y) cout << ((i&1)?y:x) << ' ' ;
else if(j==child1) cout << child1 << ' ' ;
else if(h[j]%2==i%2) cout << P[j] << ' ' ;
else cout << j << ' ' ;
}
cout << '\n' ;
if(i%2==0){
for(int j=0 ; j<n ; j++){
if(j==y || j==child1) cout << n << ' ' ;
else cout << j << ' ' ;
}
cout << '\n' ;
}
}
return 0;
}
