#include<bits/stdc++.h>
using namespace std ;
const int N = 105 ;
int n , m , deep[N] , par[N] , vis[N] , root , temp ;
vector<int> nei[N] ;
void star(){
cout << "3\n" ;
for(int i=0 ; i<n ; i++) cout << "0 " ; cout << '\n' ;
cout << "0 0 " ; for(int i=2 ; i<n ; i++) cout << i << ' ' ; cout << '\n' ;
for(int i=0 ; i<n ; i++) cout << "0 " ; cout << '\n' ;
}
void dfs(int node){
vis[node]=1 ;
bool flag = false ;
for(int i:nei[node]){
if(vis[i]) continue ;
flag = true ;
deep[i]=deep[node]+1 ; par[i]=node ; dfs(i) ;
}
if(!flag && deep[node]>=2) root = node ;
}
void dfs1(int node , int f=-1 , int l=-1){
vis[node]=1 ;
if(f!=-1) deep[f]=deep[node]+1 , par[f]=node , dfs1(f) ;
for(int i:nei[node]){
if(vis[i]) continue ;
if(i==f || i==l) continue ;
deep[i]=deep[node]+1 ; par[i]=node ; dfs1(i) ;
}
if(l!=-1 && !vis[l]) deep[l]=deep[node]+1 , par[l]=node , dfs1(l) ;
}
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) ;
}
root=-1 ; dfs(0) ;
if(root==-1){
star() ; return 0 ;
}
memset(vis,0,sizeof(vis)) ;
deep[root]=0 ; temp=par[root] ;
dfs1(root,par[root],par[par[root]]) ;
cout << 2*n << '\n' ;
for(int i=1 ; i<=2*n ; i++){
for(int j=0 ; j<n ; j++){
if(j==root || j==temp) cout << temp << ' ' ;
else if(deep[j]%2==i%2) cout << par[j] << ' ' ;
else cout << j << ' ' ;
}
cout << '\n' ;
}
return 0 ;
}
