#include <bits/stdc++.h>
#define Nmax (8195<<1)
using namespace std;
ifstream f("felinare.in");
ofstream g("felinare.out");
list <int> G[Nmax];
int n,m;
int vL[Nmax],vR[Nmax];
bitset <Nmax> viz;
bitset <Nmax> is;
int head_light[Nmax];
bool match(int x)
{
    if(viz[x]) return false;
    viz[x]=true;
    for(const auto &it:G[x])
        if(!vL[it])
        {
            vL[it]=x;
            vR[x]=it;
            return true;
        }
    for(const auto &it:G[x])
        if(match(vL[it]))
        {
            vL[it]=x;
            vR[x]=it;
            return true;
        }
    return false;
}
void cover(int x)
{
    for(const auto &it:G[x])
        if(!is[it])
        {
            is[it]=true;
            head_light[it-n]+=2;
            head_light[vL[it]]--;
            cover(vL[it]);
        }
}
int main()
{
    f>>n>>m;
    int i,j;
    while(m--)
    {
        f>>i>>j;
        G[i].push_back(j+n);
        G[j+n].push_back(i);
    }
    bool ok=true;
    while(ok)
    {
        ok=false;
        for(i=1;i<=n;i++)
            if(!vR[i])
                if(match(i)) ok=true;
    }
    int ans=0;
    for(i=1;i<=n;i++)
        if(vR[i])
        {
            ans++;
            head_light[i]++;
        }
    for(i=1;i<=n;i++)
        if(!vR[i])
            cover(i);
    g<<(n<<1)-ans<<'\n';
    for(i=1;i<=n;i++)
        g<<3-head_light[i]<<'\n';

    return 0;
}