#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

vector<int> nodes[20005];
map<int,int> mvc;
int match[20005];
bool visited[20005];

bool path(int node)
{
    int nxt;
    visited[node]=1;
    for (auto x : nodes[node])
    {
        nxt=match[x];
        if (nxt)
        {
            if (!visited[nxt] && path(nxt))
            {
                match[x]=node;
                match[node]=x;
                return 1;
            }
        }
        else
        {
            match[node]=x;
            match[x]=node;
            return 1;
        }
    }
    return 0;
}

void route(int node)
{
    for (auto x : nodes[node])
    {
        if (mvc[x]==0)
        {
            mvc[x]=1;
            if (match[x]!=0)
            {
                mvc[match[x]]=0;
                route(match[x]);
            }
        }
    }
}

signed main()
{
    ifstream fin("felinare.in");
    ofstream fout("felinare.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,i,j,u,v,cuplaj,ans;
    bool ok;
    fin >> n >> m;
    for (i=1; i<=m; i++)
    {
        fin >> u >> v;
        nodes[u].push_back(v+n);
        nodes[v+n].push_back(u);
    }
    for (i=1; i<=n*2; i++)
        match[i]=0;
    ok=1;
    cuplaj=0;
    while (ok)
    {
        ok=0;
        for (i=1; i<=n*2; i++)
            visited[i]=0;
        for (i=1; i<=n; i++)
        {
            if (!match[i] && !visited[i] && path(i))
            {
                ok=1;
                cuplaj++;
            }
        }
    }
    fout << n*2-cuplaj << "\n";
    for (i=1; i<=n; i++)
    {
        if (match[i])
            mvc[i]=1;
    }
    for (i=1; i<=n; i++)
    {
        if (!match[i])
            route(i);
    }
    for (i=1;i<=n;i++)
    {
         ans=0;
         if (!mvc[i])
             ans|=1;
         if (!mvc[i+n])
             ans|=2;
         fout << ans << "\n";
    }
    return 0;
}