#include <bits/stdc++.h>
#pragma GCC optimize("O3")

#define nozerous(x) (x & -x)
#define MOD 30103
#define M_PI           3.14159265358979323846
#define EPS 0.0001
using namespace std;

const int INF = (1 << 30), NMAX(8200);
using VI  = vector<int>;
using VVI = vector<VI>;
using VB  = vector<bool>;
using Point = array<int, 2>;

void BUNA(const string& task = "")
{
    if (!task.empty())
        freopen((task + ".in").c_str(), "r", stdin),
                freopen((task + ".out").c_str(), "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
void PA()
{
    exit(0);
}

vector<int> G[NMAX], F[2 * NMAX];
int st[2 * NMAX], dr[2 * NMAX], s1[2 * NMAX], s2[2 * NMAX];
bool viz[2 * NMAX];

inline bool cup(int nod)
{
    viz[nod] = 1;
    for(auto it: F[nod])
        if(!dr[it])
        {
            st[nod] = it;
            dr[it] = nod;
            return 1;
        }
    for(auto it: F[nod])
        if(!viz[dr[it]] && cup(dr[it]))
        {
            st[nod] = it;
            dr[it] = nod;
            return 1;
        }
    return 0;
}

void WORK(int nod)
{
    for(auto it: G[nod])
        if(s2[it] == 0)
        {
            s2[it] = 1;
            s1[dr[it]] = 0;
            WORK(dr[it]);
        }
}

int main()
{
    BUNA("felinare");
    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= m; ++i)
    {
        int x, y;
        cin >> x >> y;

        G[x].push_back(y);
        F[x].push_back(y + n);
    }

    bool ok = 1;
    do
    {
        ok = 0;
        for(int i = 1; i <= 2 * n; ++i)
            viz[i] = 0;
        for(int i = 1; i <= n; ++i)
            if(!viz[i] && !st[i])
                ok |= cup(i);
    }
    while(ok);

    int cnt = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(st[i] != 0)
        {
            ++cnt;
            st[i] -= n;
            s1[i] = 1;
        }
        dr[i] = dr[i + n];
    }

    for(int i = 1; i <= n; ++i)
        if(s1[i] == 0)
            WORK(i);

    cout << 2 * n - cnt << '\n';

    for(int i = 1; i <= n; ++i)
        if(s1[i] == 1 && s2[i] == 1)
            cout << 0 << '\n';
        else if(s1[i] == 0 && s2[i] == 1)
            cout << 1 << '\n';
        else if(s2[i] == 0 && s1[i] == 1)
            cout << 2 << '\n';
        else cout << 3 << '\n';
    PA();
}