#include <bits/stdc++.h>
using namespace std;
void sol_riga(int N, vector<int> &ord) {
cout << 2*((N+1)/2) << "\n";
for (int i = 0; i < (N+1)/2; i++) {
vector<int> col(N);
for (int j = 0; j < N; j+=2) {
col[ord[j]] = ord[j];
if (j+1 < N) col[ord[j+1]] = ord[j];
}
for (int j = 0; j < N; j++) cout << col[j] << " ";
cout << "\n";
col[ord[0]] = ord[0];
for (int j = 1; j < N; j+=2) {
col[ord[j]] = ord[j];
if (j+1 < N) col[ord[j+1]] = ord[j];
}
for (int j = 0; j < N; j++) cout << col[j] << " ";
cout << "\n";
}
}
struct sol_albero {
int N;
vector<vector<int>> adj;
vector<int> dist; //distanza di ogni nodo dalla radice
vector<int> pad; //padre di ogni nodo
void dfs(int att) {
for (int pros : adj[att]){
if (pros == pad[att]) continue;
dist[pros] = dist[att]+1;
pad[pros] = att;
dfs(pros);
}
}
void risolvi(int n, vector<vector<int>> aa, int rad, int pb, int aus) {
N = n;
adj.resize(N); dist.resize(N); pad.resize(N);
fill(pad.begin(), pad.end(), -1); fill(dist.begin(), dist.end(), 0);
for (int i = 0; i < N; i++) {
adj[i] = aa[i];
}
cout << 6*N << "\n";
dfs(rad);
for (int k = 0; k < 2*N; k++) {
for (int i = 0; i < N; i++) {
if ((dist[i]%2) == 0|| i == pb) cout << i << " ";
else cout << pad[i] << " ";
}
cout << "\n";
for (int i = 0; i < N; i++) {
if ((dist[i]%2) == 1) cout << i << " ";
else if (i == rad) cout << aus << " ";
else cout << pad[i] << " ";
}
cout << "\n";
for (int i = 0; i < N; i++) {
if (i == rad || i == pb) cout << rad << " ";
else cout << i << " ";
}
cout << "\n";
}
}
};
int main() {
//freopen("output.txt", "w", stdout);
int N, M; cin >> N >> M;
//cout << N << " " << M << "\n";
vector<vector<int>> adj(N);
vector<vector<bool>> mata(N, vector<bool> (N, 0));
for (int i = 0; i < M; i++) {
int a, b; cin >> a >> b;
//cout << a << " " << b << "\n";
adj[a].push_back(b);
adj[b].push_back(a);
mata[a][b] = 1; mata[b][a] = 1;
}
vector<int> pdr(N, -1);
vector<bool> vis(N, 0);
vector<int> prof(N, 0);
vector<vector<int>> sptr(N);
stack<int> dfs; dfs.push(0);
while (!dfs.empty()) {
int x = dfs.top(); dfs.pop();
if (vis[x]) continue;
vis[x] = 1;
if(pdr[x] != -1) {
prof[x] = prof[pdr[x]]+1;
sptr[pdr[x]].push_back(x);
sptr[x].push_back(pdr[x]);
}
for (int y : adj[x]) {
if (vis[y]) continue;
pdr[y] = x;
dfs.push(y);
}
}
fill(vis.begin(), vis.end(), 0);
bool linea = 1; int beg;
for (int i = 0; i < N; i++) {
if (sptr[i].size() > 2) linea = 0;
if (sptr[i].size() == 1) beg = i;
}
if (linea) {
vector<int> ord;
ord.push_back(beg); vis[beg] = 1;
do {
if (vis[sptr[beg][0]]) beg = sptr[beg][1];
else beg = sptr[beg][0];
ord.push_back(beg); vis[beg] = 1;
} while (sptr[beg].size() == 2);
sol_riga(N, ord);
return 0;
}
pair<int, int> gb = {0, 0};
for (int i = 0; i < N; i++) {
if (sptr[i].size() <= 2) continue;
gb = max(gb, {prof[i], i});
}
vector<int> rs;
bool pa = 1; int fp;
for (int x : sptr[gb.second]) {
if (x == pdr[gb.second]) continue;
if (mata[x][pdr[gb.second]] || !pa) {
rs.push_back(x);
continue;
}
fp = x; pa = 0;
}
if (pa) {
fp = rs[rs.size()-1];
rs.pop_back();
}
//scendo sul ramo di fp per mantenerlo una linea
vis[gb.second] = 1;
vis[fp] = 1;
int att = fp;
while (sptr[att].size() == 2) {
if (vis[sptr[att][0]]) att = sptr[att][1];
else att = sptr[att][0];
vis[att] = 1;
}
//ricalcolo lo spanning tree
for (int i = 0; i < N; i++) {
if (!vis[i] || i == gb.second) sptr[i].clear();
}
sptr[gb.second].push_back(fp);
if(pdr[gb.second] > -1) rs.push_back(pdr[gb.second]);
fill(pdr.begin(), pdr.end(), -1);
for (int i : rs) {
if (vis[i]) continue;
pdr[i] = gb.second;
sptr[i].push_back(gb.second);
sptr[gb.second].push_back(i);
dfs.push(i);
while (!dfs.empty()) {
int x = dfs.top(); dfs.pop();
if (vis[x]) continue;
vis[x] = 1;
if(pdr[x] != -1) {
sptr[pdr[x]].push_back(x);
sptr[x].push_back(pdr[x]);
}
for (int y : adj[x]) {
if (vis[y]) continue;
pdr[y] = x;
dfs.push(y);
}
}
}
sol_albero d;
if (sptr[fp].size() == 1) d.risolvi(N, sptr, fp, -1, gb.second);
else if (sptr[fp][0] == gb.second) d.risolvi(N, sptr, fp, sptr[fp][1], gb.second);
else d.risolvi(N, sptr, fp, sptr[fp][0], gb.second);
}
