#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,a,b) for (int i = a; i >= b; i--)
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define endl '\n'
const int MAXN = 5e3+10;
const int INF = 1e18+10;
const int MOD = 998244353;
vector<int> g[MAXN], lvl[MAXN];
int h[MAXN], H;
void dfs(int u, int p = -1) {
H=max(H,h[u]);
lvl[h[u]].pb(u);
for(int &v : g[u]) if (v!=p) {
h[v] = h[u] +1;
dfs(v,u);
}
}
void solve() {
int n,m; cin >> n >> m;
rep(i,1,m) {
int u, v; cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
dfs(0);
vector<vector<int>> ans;
vector<int> col(n);
per(i,H+1,1) {
for(int &x : lvl[i]) col[x] = i;
ans.pb(col);
}
cout << 2*ans.size() << endl;
rep(_,1,2) {
rep(i,0,H) {
for(int &x : ans[i]) cout << x << ' ';
cout << endl;
}
}
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(nullptr);
int tt = 1;
//cin >> tt;
while (tt--) solve();
return 0;
}
