#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <set>
#include <queue>
#include <bitset>
#define ll long long
using namespace std;
ifstream fin("felinare.in");
ofstream gout("felinare.out");
vector<vector<int>>g(8195);
int n,m,e,maxMatch;
bitset<8195>viz(0);
vector<int>l(8195),r(8195),sl(8195),sr(8195);

bool match(int x)
{
    if(viz[x])return 0;
    viz[x]=1;
    for(const auto &y:g[x])if(!l[y]||match(l[y]))
        {
            l[x]=y;
            r[y]=x;
            sl[x]=1;
            return 1;
        }
    return 0;
}
void hk()
{
    bool changed=1;
    int i;
    while(changed)
    {
        changed=0;
        viz.reset();
        for(i=1; i<=n; ++i)if(!l[i]&&match(i))
            {
                changed=1;
                ++maxMatch;
            }
    }
}
void suport(int x)
{
    for(const auto &y:g[x])if(!sr[y])
        {
            sr[y]=1;
            sl[l[y]]=0;
            suport(l[y]);
        }
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    gout.tie(0);
    int a,b,i;
    fin>>n>>m;
    while(m--)
    {
        fin>>a>>b;
        g[a].push_back(b);
    }
    hk();
    for(i=1; i<=n; ++i)if(!sl[i])suport(i);
    gout<<n*2-maxMatch<<'\n';
    for(i=1; i<=n; ++i)gout<<3-sl[i]-2*sr[i]<<'\n';
    return 0;
}