#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int n, m;
vector<int> g[N];
int deep[N], par[N], vis[N], deg[N];
int root, x;
// 建 DFS tree
void dfs(int u){
vis[u]=1;
for(int v:g[u]){
if(vis[v]) continue;
par[v]=u;
deep[v]=deep[u]+1;
deg[u]++;
dfs(v);
}
if(deg[u]>1 && deep[u]>deep[x]) x=u;
}
// path 情況（2N）
void solve_line(){
cout << 2*n << '\n';
for(int i=0;i<2*n;i++){
for(int v=0;v<n;v++){
if(v==root || deep[v]%2==i%2) cout << v << ' ';
else cout << par[v] << ' ';
}
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;
g[a].push_back(b);
g[b].push_back(a);
}
// 找一個 far node 當 root
dfs(0);
root = max_element(deep, deep+n) - deep;
// 重建 DFS
memset(vis,0,sizeof(vis));
memset(par,-1,sizeof(par));
memset(deg,0,sizeof(deg));
deep[root]=0;
x=root;
dfs(root);
// 如果是 path
if(*max_element(deep,deep+n)==n-1){
solve_line();
return 0;
}
// 找 q = x
// 找 r0（x 的某個 child）
int r0=-1;
for(int v:g[x]){
if(v!=par[x]){
r0=v;
break;
}
}
// 🔥 控制 DFS 順序
// r0 先走到 x
auto &vr = g[r0];
auto it = find(vr.begin(), vr.end(), x);
if(it!=vr.end()) swap(vr[0], *it);
// x：先走 children，再走 parent
auto &vx = g[x];
auto itp = find(vx.begin(), vx.end(), par[x]);
if(itp!=vx.end()) swap(*itp, vx.back());
// 重新 DFS（以 r0 為 root）
memset(vis,0,sizeof(vis));
memset(par,-1,sizeof(par));
memset(deg,0,sizeof(deg));
deep[r0]=0;
dfs(r0);
// 找 level 1 node（bridge 用）
int child=-1;
for(int i=0;i<n;i++){
if(par[i]==r0){
child=i;
break;
}
}
// 輸出 3N
cout << 3*n << '\n';
for(int i=0;i<2*n;i++){
// odd / even
for(int v=0;v<n;v++){
if(v==r0) cout << r0 << ' ';
else if(deep[v]%2==i%2) cout << par[v] << ' ';
else cout << v << ' ';
}
cout << '\n';
// bridge（只連 root 和 level1）
if(i%2==0){
for(int v=0;v<n;v++){
if(v==r0 || v==child) cout << n << ' ';
else cout << v << ' ';
}
cout << '\n';
}
}
return 0;
}
