#include<bits/stdc++.h>
using namespace std;
vector<int> haha[1001];
vector<int> tree[1001];
vector<bool> bruh(1001,true);
vector<int> dep[1001];
vector<int> par(1001);
vector<pair<int,int>> troll(0);
vector<vector<int>> ans(0);
void dfs(int a, int t) {
par[a] = t;
if(t != -1) {
troll.push_back({t,a});
}
for(int v: tree[a]) {
dfs(v,a);
}
if(t != -1) {
troll.push_back({t,a});
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m,a,b;
cin >> n >> m;
for(int i = 0; i < m; i++) {
cin >> a >> b;
haha[a].push_back(b);
haha[b].push_back(a);
}
if(m == n*(n-1)/2) {
int ans[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
ans[i][j] = j;
}
}
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
ans[(i+j)%n][i] = ans[(i+j)%n][j];
}
}
cout << 2*n << "\n";
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout << ans[i][j] << " ";
}
cout << "\n";
for(int j = 0; j < n; j++) {
cout << ans[i][j] << " ";
}
cout << "\n";
}
}
else {
int r;
for(int i = 0; i < n; i++) {
if(haha[i].size() < n-1) {
r = i;
break;
}
}
vector<int> idk(1,r);
int y = 0;
dep[0].push_back(r);
bruh[r] = false;
while(true) {
vector<int> idk2(0);
for(int u: idk) {
for(int v: haha[u]) {
if(bruh[v]) {
idk2.push_back(v);
dep[y+1].push_back(v);
bruh[v] = false;
tree[u].push_back(v);
}
}
}
if(idk2.empty()) {
break;
}
idk = idk2;
y++;
}
dfs(r,-1);
for(int i = n-(n%2); i >= 2; i-=2) {
vector<int> wut(n);
for(int v: dep[i]) {
for(int j = 0; j < n; j++) {
wut[j] = j;
}
wut[v] = par[par[v]];
wut[par[v]] = par[par[v]];
ans.push_back(wut);
for(int j = 0; j < n; j++) {
wut[j] = j;
}
wut[par[v]] = par[par[v]];
ans.push_back(wut);
}
}
for(int i = 0; i < troll.size(); i++) {
vector<int> wut(n);
for(int j = 0; j < n; j++) {
wut[j] = j;
}
wut[troll[i].first] = troll[i].second;
ans.push_back(wut);
}
for(int i = ans.size()-troll.size()-1; i >= 0; i--) {
ans.push_back(ans[i]);
}
for(int i = n-(n%2)+1; i >= 3; i-=2) {
vector<int> wut(n);
for(int v: dep[i]) {
for(int j = 0; j < n; j++) {
wut[j] = j;
}
wut[v] = par[par[v]];
wut[par[v]] = par[par[v]];
ans.push_back(wut);
for(int j = 0; j < n; j++) {
wut[j] = j;
}
wut[par[v]] = par[par[v]];
ans.push_back(wut);
}
}
int x = dep[2][0];
for(int v: dep[1]) {
if(v != x) {
vector<int> wut(n);
for(int j = 0; j < n; j++) {
wut[j] = j;
}
wut[x] = par[x];
ans.push_back(wut);
for(int j = 0; j < n; j++) {
wut[j] = j;
}
wut[v] = r;
ans.push_back(wut);
for(int j = 0; j < n; j++) {
wut[j] = j;
}
wut[par[x]] = r;
wut[x] = r;
ans.push_back(wut);
}
}
vector<int> wut(n);
for(int j = 0; j < n; j++) {
wut[j] = j;
}
wut[par[x]] = r;
cout << ans.size() << "\n";
for(vector<int> wut: ans) {
for(int i = 0; i < n; i++) {
cout << wut[i] << " ";
}
cout << "\n";
}
}
return 0;
}
