#include <bits/stdc++.h>
using namespace std;
const char nl = '\n';
const char sp = ' ';
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const char out[2][4]{ "NO", "YES" };
#define all(a) a.begin(), a.end()
using ll = long long;
ifstream fin("felinare.in");
ofstream fout("felinare.out");

/*

Consider cele 2 felinare ale fiecarei intersectii drept noduri, iar strazile drept muchii intre noduri

Aprind numarul maxim de felinare astfel incat sa acopar toate strazile => Maximum Vertex Cover

Cautam Maximum Bipartite Matching pe graful construit si cu ajutorul acesteia construim Maximum Vertex Cover

*/

const int nmax = 8191;
int n, m;
vector<int> g[nmax * 2 + 5];
int match[nmax * 2 + 5]{ 0 };
bool vis[nmax * 2 + 5]{ 0 };
bool color[nmax * 2 + 5]{ 0 };

int f_in(int u) { return u * 2; }

int f_out(int u) { return u * 2 - 1; }

void add_edge(int u, int v) {
    match[match[u]] = 0;
    match[match[v]] = 0;
    match[u] = v;
    match[v] = u;
}

bool find_matching(int u) {
    vis[u] = true;
    for (auto& v : g[u]) {
        if (match[v] == 0 || (!vis[match[v]] && find_matching(match[v]))) {
            add_edge(u, v);
            return true;
        }
    }
    return false;
}

void spread(int u) {
    color[u] = 1;
    for (auto& v : g[u]) {
        if (color[v]) {
            continue;
        }
        color[v] = 1;
        if (match[v]) {
            spread(match[v]);
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        fin >> u >> v;
        g[f_out(u)].push_back(f_in(v));
        g[f_in(v)].push_back(f_out(u));
    }
    // pornim de la un cuplaj ales greedy
    for (int i = 2; i <= 2 * n; i += 2) {
        for (auto& j : g[i]) {
            if (match[j] == 0) {
                add_edge(i, j);
                break;
            }
        }
    }
    for (int i = 2; i <= 2 * n; i += 2) {
        if (match[i] == 0) {
            fill(vis + 1, vis + 2 * n + 1, 0);
            find_matching(i);
        }
    }
    // am gasit cuplajul maxim, caut minimum vertex cover
    for (int i = 1; i <= 2 * n; i += 2) {
        if (match[i] == 0) {
            spread(i);
        }
    }
    for (int i = 2; i <= 2 * n; i += 2) {
        color[i] ^= 1;
    }
    fout << count(color + 1, color + 2 * n + 1, 1) << nl;
    for (int i = 1; i <= n; ++i) {
        fout << color[f_out(i)] + 2 * color[f_in(i)] << nl;
    }
}