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

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

void matching()
{
    bool better = true;
    while(better)
    {
        better = false;
        memset(vis, false, sizeof(vis));
        for(int i = 1; i <= n; i++)
            better |= (pair_L[i] == 0 && dfs(i) == true);
    }
}

void atribuire(int node)
{
    if(vis[node] == true)
        return;
    vis[node] = true;
    for(int next : adj[node])
    {
        if(pair_L[node] != next && in_mvc[next] == false)
        {
            in_mvc[next] = true;
            atribuire(pair_R[next]);
        }
    }
}

int main()
{
    fin >> n >> m;
    while(m--)
    {
        int u, v;
        fin >> u >> v;
        adj[u].push_back(v);
    }
    matching();
    memset(vis, false, sizeof(vis));
    int ans = 2 * n;
    for(int i = 1; i <= n; i++)
    {
        if(pair_L[i])
            ans--;
        else
            atribuire(i);
    }
    fout << ans << "\n";
    for(int i = 1; i <= n; i++)
        fout << vis[i] + 2 * (1 - in_mvc[i]) << "\n";

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