#include<bits/stdc++.h>
using namespace std ;
const int N = 105 ;
int n , m , arr[N][N] , deep[N] , par[N] , deg[N] , vis[N] , x , root , child ;
vector<int> nei[N] ;
bool flag ;
void line(){
cout << 2*n << '\n' ;
for(int i=0 ; i<2*n ; i++){
for(int j=0 ; j<n ; j++){
if(j==root || i%2==deep[j]%2) cout << j << ' ' ;
else cout << par[j] << ' ' ;
}
cout << '\n' ;
}
}
void dfs(int node){
vis[node]=1 ;
for(int i:nei[node]){
if(vis[i]) continue ;
deg[node]++ ; deep[i]=deep[node]+1 ; par[i]=node ; dfs(i) ;
}
}
void dfs1(int node , int a){
vis[node]=1 ;
if(a!=-1 && arr[node][a] && !vis[a]) deep[a]=deep[node]+1 , par[a]=node , dfs1(a,a) ;
for(int i:nei[node]){
if(vis[i]) continue ;
if(i==a) continue ;
deep[i]=deep[node]+1 ; par[i]=node ; dfs1(i,a) ;
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) ;
cin >> n >> m ;
for(int i=0 ; i<m ; i++){
int a , b ; cin >> a >> b ;
nei[a].push_back(b) ; nei[b].push_back(a) ;
arr[a][b]=arr[b][a]=1 ;
}
dfs(0) ;
root = max_element(deep,deep+n)-deep ; deep[root] = 0 ;
memset(par,-1,sizeof(par)) ; memset(vis,0,sizeof(vis)) ; memset(deg,0,sizeof(deg)) ;
x = root ; dfs(root) ;
for(int i=0 ; i<n ; i++){
if(deg[i]>1 && deep[i]>deep[x]) x = i ;
}
if(*max_element(deep,deep+n)==n-1){
line() ; return 0 ;
}
// want to find a spanning tree such that it is similar to the case of tree
// if doesn't exist the root can achieve the goal , we need to construct one
root = -1 ;
memset(vis,0,sizeof(vis)) ;
for(int i:nei[par[x]]) vis[i]=1 ;
for(int i=0 ; i<n ; i++){
if(par[i]==x && (root==-1 || !vis[i])) root = i ;
}
vector<int> path ;
child = root ;
while(true){
int temp = -1 ;
for(int i=0 ; i<n ; i++){
if(par[i]==child){
temp = i ; break ;
}
}
if(temp==-1) break ;
path.push_back(temp) ;
child = temp ;
}
if(path.empty()) child = -1 ;
else child = path[0] ;
memset(vis,0,sizeof(vis)) ;
for(int i:path) vis[i]=1 ;
sort(nei[x].begin(),nei[x].end(),[&](int v , int u){
if((par[v]==x)!=(par[u]==x)) return (par[v]==x)>(par[u]==x) ;
return v<u ;
});
deep[root]=0 ; dfs1(root,x) ;
for(int i=0 ; i<path.size() ; i++) deep[path[i]]=i+1 , par[path[i]]=(i?path[i-1]:root) ;
cout << 6*n << '\n' ;
for(int i=1 ; i<=4*n ; i++){
for(int j=0 ; j<n ; j++){
if(j==root) cout << ((i&1)?root:x) << ' ' ;
else if(j==child) cout << child << ' ' ;
else if(deep[j]%2==i%2) cout << par[j] << ' ' ;
else cout << j << ' ' ;
}
cout << '\n' ;
if(i%2==0){
for(int j=0 ; j<n ; j++){
if(j==root || j==child) cout << n << ' ' ;
else cout << j << ' ' ;
}
cout << '\n' ;
}
}
return 0 ;
}
