//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;
if(!vis2[y]) swap(g[x][0],*find(g[x].begin(),g[x].end(),P[x]));
else 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); vector<bool> onPath(n,false);
for(int i=0; i<(ll)path.size(); i++) h[path[i]]=i+1, onPath[path[i]]=true, P[path[i]]=(i?path[i-1]:y);
cout << 6*n << "\n"; ll ans;
for(int i=0; i<6*n; i++){
for(int v=0; v<n; v++){
if(i%3==0){
if(h[v]%2==1 && (path.empty() || v!=path[0])) ans=P[v];
else ans=v;
}else if(i%3==1){
if(v==y) ans=x;
else if(h[v]%2==0) ans=P[v];
else ans=v;
}else{
if(!path.empty() && v==path[0]) ans=y;
else ans=v;
}
cout << ans << " ";
}
cout << "\n";
}
return 0;
}
