#include<bits/stdc++.h>
using namespace std ;
const int N = 105 ;
int n , m , deep[N] , par[N] , deg[N] , vis[N] , x , root ;
vector<int> nei[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) ;
}
if(deg[node]>1 && deep[node]>deep[x]) x = node ;
}
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' ;
}
}
int main(){
ios::sync_with_stdio(0),cin.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) ;
}
// 找直徑端點
dfs(0) ;
root = max_element(deep,deep+n)-deep ;
memset(vis,0,sizeof(vis));
memset(par,-1,sizeof(par));
memset(deg,0,sizeof(deg));
x = root ;
deep[root]=0 ;
dfs(root) ;
// path case
if(*max_element(deep,deep+n)==n-1){
line() ;
return 0 ;
}
// 找 q = x
// 找 r0 = 任一 child of x
int r0 = -1 ;
for(int v:nei[x]){
if(v!=par[x]){
r0 = v ;
break ;
}
}
// 🔥 關鍵：調整 DFS 順序
// 讓 r0 先走到 x，再展開
// swap adjacency
auto &v = nei[r0] ;
auto it = find(v.begin(),v.end(),x);
if(it!=v.end()) swap(v[0],*it);
// 重新 DFS
memset(vis,0,sizeof(vis));
memset(par,-1,sizeof(par));
deep[r0]=0 ;
dfs(r0);
// bridge endpoint = root 的 child
int child = -1 ;
for(int i=0;i<n;i++){
if(par[i]==r0){
child=i;
break;
}
}
cout << 3*n << '\n';
for(int i=0;i<2*n;i++){
// odd / even
for(int j=0;j<n;j++){
if(j==r0) cout << r0 << ' ';
else if(deep[j]%2==i%2) cout << par[j] << ' ';
else cout << j << ' ';
}
cout << '\n';
// bridge
if(i%2==0){
for(int j=0;j<n;j++){
if(j==r0 || j==child) cout << n << ' ';
else cout << j << ' ';
}
cout << '\n';
}
}
}
