#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll N, M;
cin >> N >> M;
vector<vector<ll> > adjList(N);
for (ll i = 0; i < M; i++) {
ll ui, vi;
cin >> ui >> vi;
adjList[ui].push_back(vi);
adjList[vi].push_back(ui);
}
ll root = -1;
ll neighborRoot = -1;
for (ll i = 0; i < N; i++) {
if (adjList[i].size() == 1) {
root = i;
neighborRoot = adjList[i][0];
break;
}
}
set<ll> even, odd;
vector<ll> depth(N, -1);
vector<ll> parent(N, -1);
vector<bool> visited(N, false);
queue<pair<ll, ll> > bfs;
bfs.push({0, root});
while (!bfs.empty()) {
auto [d, v] = bfs.front();
bfs.pop();
depth[v] = d;
visited[v] = true;
if (d % 2 == 0) even.insert(v);
else odd.insert(v);
for (auto &l: adjList[v]) {
if (!visited[l]) {
bfs.push({d + 1, l});
visited[l] = true;
parent[l] = v;
}
}
}
even.erase(root);
cout << 2 * N << endl;
for (ll i = 0; i < 2 * N; i++) {
vector<ll> colors(N, 0);
if (i % 2 == 0) {
for (auto &l: even) {
colors[l] = depth[l];
}
for (auto &l: odd) {
colors[l] = colors[parent[l]];
}
} else {
for (auto &l: odd) {
colors[l] = depth[l];
}
for (auto &l: even) {
colors[l] = colors[parent[l]];
}
colors[root] = colors[neighborRoot];
}
for (ll j = 0; j < N; j++) {
if (j != 0) cout << " ";
cout << colors[j];
}
cout << endl;
}
}
