#include <bits/stdc++.h>

using namespace std;

const int NMAX = 30000;
int N, M;
vector <int> graph[NMAX];
int l[NMAX], r[NMAX];
bitset <NMAX> seen;
bool lightL[NMAX], lightR[NMAX];

bool Match(int node)
{
    if (seen[node] == 1)
        return false;
    seen[node] = 1;
    for (auto& x : graph[node])
    {
        if (r[x] == 0)
        {
            l[node] = x;
            r[x] = node;
            return true;
        }
    }
    for (auto& x : graph[node])
    {
        if (Match(r[x]))
        {
            l[node] = x;
            r[x] = node;
            return true;
        }
    }
    return false;
}

void dfs(int node)
{
    for (auto& x : graph[node])
    {
        if (lightR[x] == false)
        {
            lightR[x] = true;
            dfs(r[x]);
        }
    }
}

int main()
{
    ifstream fin("felinare.in");
    ofstream fout("felinare.out");
    fin >> N >> M;
    for (int i = 1;i <= M;++i)
    {
        int u, v;
        fin >> u >> v;
        graph[u].push_back(v);
    }
    bool ok = true;
    int answer = 0;
    while (ok)
    {
        ok = false;
        for (int i = 1;i <= N;++i)
            seen[i] = 0;
        for (int i = 1;i <= N;++i)
            if (l[i] == 0 && Match(i))
            {
                ++answer;
                ok = true;
            }
    }
    for (int i = 1;i <= N;++i)
        if (l[i] == 0)
            dfs(i);
    for (int i = 1;i <= N;++i)
        if (l[i] != 0 && lightR[l[i]] == false)
            lightL[i] = true;
    fout << 2 * N - answer << "\n";
    for (int i = 1;i <= N;++i)
    {
        if (lightL[i] == true && lightR[i] == true)
            fout << 0 << "\n";
        else if (lightL[i] == false && lightR[i] == true)
            fout << 1 << "\n";
        else if (lightL[i] == true && lightR[i] == false)
            fout << 2 << "\n";
        else
            fout << 3 << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}