// 放て！心に刻んだ夢を
// 未来さえ置き去りにして
// 限界など知らない　意味無い
// この能力が光散らす
// その先に遥かな想いを
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ul unsigned ll
#define LL __int128_t
#define db double
#define DB long db
#define pii pair<int, int>
#define pil pair<int, ll>
#define fi first
#define se second
#define mkpr make_pair
#define vi vector<int>
#define vii vector<pii>
#define vil vector<pil>
#define eb emplace_back
#define all(c) (c).begin(), (c).end()
#define bit(x) (1 << (x))
#define bin(s, x) ((s) >> (x) & 1)
#define mem(a, x) memset(a, x, sizeof(a))
#define req(i, l, r) for (int i(l), i##End(r); i < i##End; i = -~i)
#define qer(i, r, l) for (int i(r), i##End(l); i > i##End; i = ~-i)
#define rep(i, l, r) for (int i(l), i##End(r); i <= i##End; i = -~i)
#define per(i, r, l) for (int i(r), i##End(l); i >= i##End; i = ~-i)

#ifdef JYR
#define errs(x) fputs(x "\n", stderr)
#define errm(x, ...) fprintf(stderr, x, ##__VA_ARGS__)
#else
#define errs(x) 0
#define errm(x, ...) 0
#endif

template<typename T, typename U> void chkmx(T &_a, U _b) { if (_a < _b) _a = _b; }
template<typename T, typename U> void chkmn(T &_a, U _b) { if (_a > _b) _a = _b; }
template<typename T> T sq(T x) { return x * x; }

bool Mbe;

// #define MC

#define N 105
#define mod 998244353
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f

int n, m;
vector<int> H[N], G[N];
int a[N];
int de[N], fa[N];
int pt[N], tt;
bool g[N][N], vs[N];

void dfs(int u) {
    vs[u] = 1, pt[++tt] = u;
    for (auto v : G[u]) if (!vs[v])
        de[v] = de[u] + 1, fa[v] = u, dfs(v);
    rep(v, 1, n)  if (g[u][v] && !vs[v])
        de[v] = de[u] + 1, fa[v] = u, dfs(v);
}

void mslv() {
    scanf("%d%d", &n, &m);
    rep(i, 1, m) {
        int u, v;
        scanf("%d%d", &u, &v);
        u++, v++;
        g[u][v] = g[v][u] = 1;
    }
    puts("600"), de[0] = -1, dfs(1);
    rep(i, 1, n) H[fa[i]].eb(i);
    bool fg = 1;
    rep(i, 1, n) fg &= H[i].size() <= 1;
    if (fg) {
        per(i, 600, 1) {
            iota(a + 1, a + n + 1, 1);
            rep(j, 2, n) if (bin(de[pt[j]], 0) == bin(i, 0))
                a[pt[j]] = a[fa[pt[j]]];
            rep(j, 1, n) printf("%d%c", a[j], " \n"[j == n]);
        }
        return;
    }
    int q = 0, u, p;
    rep(i, 1, n) if (H[i].size() > 1)
        if (de[q] < de[i]) q = i;
    u = H[q][0], p = fa[q];
    for (auto v : H[q]) if (!g[v][p]) u = v;
    memset(vs, 0, sizeof vs);
    if (!H[u].empty()) {
        int v = u;
        while (!H[v].empty()) v = H[v][0], vs[v] = 1;
    }
    G[u].eb(q), G[q] = H[q];
    if (p) G[q].eb(p);
    tt = 0, fa[u] = 0, de[u] = 0, dfs(u);
    if (!H[u].empty()) {
        int v = u;
        while (!H[v].empty()) {
            de[H[v][0]] = de[v] + 1;
            pt[++tt] = v = H[v][0];
        }
    }
    per(i, 600, 1) {
        iota(a + 1, a + n + 1, 1);
        if ((i % 3) <= 1) a[q] = a[u];
        rep(j, 3, n) if ((fa[pt[j]] == u ? 2 : bin(de[pt[j]], 0)) == i % 3)
            a[pt[j]] = a[fa[pt[j]]];
        rep(j, 1, n) printf("%d%c", a[j], " \n"[j == n]);
    }
}

void sprw() {}

void mprw() {}

bool Med;

int main() {
    #ifdef JYR
    freopen("Test.in", "r", stdin);
    freopen("Test.out", "w", stdout);
    #endif
    mprw();
    #ifdef MC
    int _; scanf("%d", &_);
    while (_--) sprw(), mslv();
    #else
    mslv();
    #endif
    errm("%.3lfMB %.0lfms\n", abs(&Med - &Mbe) / 1048576., clock() * 1000. / CLOCKS_PER_SEC);
    return 0;
}