#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n);
vector<vector<int>> adj(n, vector<int>(n, 0));
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
if (x == y || adj[x][y]) continue;
g[x].push_back(y);
g[y].push_back(x);
adj[x][y] = adj[y][x] = 1;
}
if (!count_if(g.begin(), g.end(), [&](const vector<int>& v) { return v.size() < n - 1; })) {
int q = n + (n % 2);
vector<int> circ(q), col(q, 0);
iota(circ.begin(), circ.end(), 0);
cout << 2 * (q - 1) << endl;
for (int _ = 0; _ < q - 1; _++) {
for (int i = 0; i < q / 2; i++) {
col[circ[i]] = col[circ[q - 1 - i]] = i;
}
for (int i = 0; i < n; i++) cout << col[i] << ' ';
cout << endl;
for (int i = 0; i < n; i++) cout << col[i] << ' ';
cout << endl;
rotate(circ.begin() + 1, circ.begin() + 2, circ.end());
}
return 0;
}
auto go = [&]() {
for (int r = 0; r < n; r++) {
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
if (r != x && r != y && x != y) {
if (adj[r][x] == 1 && adj[r][y] == 1 && adj[x][y] == 0) {
g[r].insert(g[r].begin(), {x, y});
return r;
}
}
}
}
}
return -1;
};
int root = go();
assert(root != -1);
vector<vector<int>> childs(n);
vector<int> par(n, -1);
par[root] = -2;
queue<int> q;
q.push(root);
while (!q.empty()) {
int x = q.front(); q.pop();
for (int y : g[x]) {
if (par[y] == -1) {
childs[x].push_back(y);
par[y] = x;
q.push(y);
}
}
}
for (int x : childs[root]) {
vector<int> bad;
for (int y : childs[root]) {
if (adj[x][y]) bad.push_back(y);
}
for (int y : bad) {
childs[root].erase(remove(childs[root].begin(), childs[root].end(), y), childs[root].end());
childs[x].push_back(y);
par[y] = x;
}
}
vector<vector<int>> ans;
vector<int> free(n, 0);
free[root] = 1;
while (accumulate(free.begin(), free.end(), 0) < n - 1) {
vector<int> col(n), active(free), nfree(free);
iota(col.begin(), col.end(), 1);
if (!free[root]) {
int best = 1e9, b = -1;
for (int x : childs[root]) {
int pending = count_if(childs[x].begin(), childs[x].end(), [&](int y) { return !free[y]; });
if (free[x] && pending < best) {
best = pending;
b = x;
}
}
active[b] = 0;
col[b] = col[root];
nfree[b] = 0;
nfree[root] = 1;
} else {
active[root] = 1e9;
}
for (int x = 0; x < n; x++) {
if (x != root && !free[x] && active[par[x]] >= 1) {
col[x] = col[par[x]];
active[par[x]]--;
nfree[x] = 1;
nfree[par[x]] = 0;
}
}
ans.push_back(col);
free = nfree;
}
assert(!free[root]);
function<void(int)> dfs = [&](int x) {
for (int y : childs[x]) {
vector<int> col(n);
iota(col.begin(), col.end(), 1);
col[y] = col[x];
ans.push_back(col);
dfs(y);
ans.push_back(col);
}
};
dfs(root);
cout << ans.size() << endl;
for (const auto& col : ans) {
for (int c : col) cout << c << ' ';
cout << endl;
}
return 0;
}
