#include <bits/stdc++.h>

using namespace std;

FILE *F=fopen("felinare.in", "r"), *G=fopen("felinare.out", "w");

int n, m, v[8193], dist[8193], pairu[8193], pairv[8193], x, y, ans;
bitset<8193> sr;
bitset<8193> sl;
vector<int> a[8193];
queue <int> q;
const int inf = 2000000000;

int bfs()
{
    vector<int> :: iterator it;
    for(int i = 1; i <= n; ++ i)
        if(!pairu[i]) dist[i] = 0, q.push(i);
        else dist[i] = inf;
    dist[0] = inf;
    int u;
    while(!q.empty())
    {
        u = q.front();
        q.pop();
        if(!u) continue;
        for(it = a[u].begin(); it != a[u].end(); ++ it)
            if(dist[pairv[*it]] == inf)
                dist[pairv[*it]] = dist[u] + 1, q.push(pairv[*it]);
    }
    return (dist[0] != inf);
}

int dfs(int nod)
{
    vector<int> :: iterator it;
    if(!nod) return 1;

    for(it = a[nod].begin(); it != a[nod].end(); ++ it)
        if(dist[pairv[*it]] == dist[nod] + 1)
            if(dfs(pairv[*it]))
            {
                pairv[*it] = nod;
                pairu[nod] = *it;
                return 1;
            }
    dist[nod] = inf;
    return 0;
}

void sup(int nod)
{
    vector<int> :: iterator it;
    for(it = a[nod].begin(); it != a[nod].end(); ++ it)
        if(!sl[*it])
        {
            sl[*it] = 1;
            sr[pairv[*it]] = 0;
            sup(pairv[*it]);
        }
}

int main()
{
    fscanf(F, "%d %d ", &n, &m);
    for(int i = 1; i <= m; ++ i)
    {
        fscanf(F, "%d %d ", &x, &y);
        a[x].push_back(y);
    }
    while(bfs())
        for(int i = 1; i <= n; ++ i)
            if(!pairu[i] && dfs(i));
    for(int i = 1; i <= n; ++ i) if(pairu[i]) sl[i] = 1;
    for(int i = 1; i <= n; ++ i) if(!pairu[i]) sup(i);
    for(int i = 1; i <= n; ++ i)
    {
        if(sl[i])
        {
            if(sr[i])
                v[i] = 0;
            else v[i] = 2, ans ++;
        }
        else
        {
            if(!sr[i])
                v[i] = 3, ans += 2;
            else v[i] = 1, ans ++;
        }
    }
    fprintf(G, "%d\n", ans);
    for(int i = 1; i <= n; ++ i)
        fprintf(G, "%d\n", v[i]);
    return 0;
}