#include <bits/stdc++.h>
using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");
const int NMAX = 8192;
int n, m, L[NMAX], R[NMAX];
bool vis[NMAX], in_mvc[NMAX];
vector<int> adj[NMAX];

bool dfs(int node)
{
    if(vis[node])
        return false;
    vis[node] = true;
    for(int next : adj[node])
    {
        if(R[next] == 0 || dfs(R[next]) == true)
        {
            L[node] = next;
            R[next] = node;
            return true;
        }
    }
    return false;
}

void min_vertex_cover(int node)
{
    if(vis[node])
        return;
    vis[node] = true;
    for(int next : adj[node])
    {
        if(L[node] != next && !in_mvc[next])
        {
            in_mvc[next] = true;
            min_vertex_cover(R[next]);
        }
    }
}

int main()
{
    fin >> n >> m;
    while(m--)
    {
        int u, v;
        fin >> u >> v;
        adj[u].push_back(v);
    }

    while(true)
    {
        bool ok = true;
        memset(vis, false, sizeof(vis));
        for(int i = 1; i <= n; i++)
            if(L[i] == 0 && dfs(i) == true)
                ok = false;
        if(ok == true)
            break;
    }

    memset(vis, false, sizeof(vis));
    int ans = 2 * n;
    for(int i = 1; i <= n; i++)
    {
        if(L[i] != 0)
            ans--;
        else
            min_vertex_cover(i);
    }
    fout << ans << "\n";
    for(int i = 1; i <= n; i++)
    {
        int tip = 0;
        if(vis[i])
            tip++;
        if(!in_mvc[i])
            tip += 2;
        fout << tip << "\n";
    }

    fin.close();
    fout.close();
    return 0;
}