#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define deb(n) cout << #n << "=" << n << " "
#define debug(n) cout << #n << "=" << n << endl
#define div() cout << "_______________" << endl
const int N = 1e3 + 10;
int n, m, ans;
int tot, T[N], vis[N], ma[N], V[N], F[N];
vector<int> v[N];
queue<int> q;
int Find(int x) {
if (F[x] == x) return x;
return F[x] = Find(F[x]);
}
int LCA(int x, int y) {
tot++;
while (1) {
if (x) {
x = Find(x);
if (T[x] == tot) return x;
T[x] = tot, x = V[ma[x]];
}
swap(x, y);
}
}
void flower(int x, int y, int p) {
while (Find(x) != p) {
V[x] = y, y = ma[x], vis[y] = 1, q.push(y);
if (Find(x) == x) F[x] = p;
if (Find(y) == y) F[y] = p;
x = V[y];
}
}
void bfs(int st) {
for (int i = 1; i <= n; i++) V[i] = vis[i] = 0, F[i] = i;
while (q.size()) q.pop();
vis[st] = 1, q.push(st);
while (q.size()) {
int x = q.front(); q.pop();
for (auto& y : v[x]) if (Find(y) != Find(x) && vis[y] != 2) {
if (vis[y] == 1) {
int l = LCA(x, y);
flower(x, y, l);
flower(y, x, l);
continue;
}
vis[y] = 2, V[y] = x;
if (!ma[y]) {
int px = y;
while (px) {
int py = V[px], pz = ma[py];
ma[px] = py, ma[py] = px, px = pz;
}
ans++;
return;
}
vis[ma[y]] = 1, q.push(ma[y]);
}
}
}
void oper() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b; cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
for (int i = 1; i <= n; i++) if (!ma[i]) bfs(i);
cout << ans << endl;
for (int i = 1; i <= n; i++) cout << ma[i] << " \n"[i == n];
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1; //cin >> t;
while (t--) oper();
return 0;
}