using namespace std;
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define Nm (1<<13)
#define Mm 20000
bool Viz[Nm<<1];
int *G[Nm<<1],D[Nm<<1],Match[Nm<<1],X[Mm],Y[Mm],n,m,d;
int Q[Nm<<1],Dm[Nm<<1];

void read()
{
    int i;

    freopen("felinare.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(i=0;i<m;++i)
    {
        scanf("%d%d",X+i,Y+i);
        Y[i]+=n;
        ++D[X[i]]; ++D[Y[i]];
    }
}

int BFS()
{
    int l=0,r=-1,i,x,ans=0;

    memset(Dm+1,0,(n<<1)*sizeof(int));
    for(i=1;i<=n;++i)
        if(!Match[i])
        {
            Dm[i]=1;
            Q[++r]=i;
        }

    while(l<=r)
    {
        x=Q[l++];
        if(x>n)
        {
            if(!Match[x])
            {
                if(!ans)
                    ans=Dm[x];
            }
            else
            {
                Q[++r]=Match[x];
                Dm[Match[x]]=Dm[x]+1;
            }
            continue;
        }
        
        for(i=0;i<D[x];++i)
            if(!Dm[G[x][i]])
            {
                Q[++r]=G[x][i];
                Dm[G[x][i]]=Dm[x]+1;
            }
    }

    return ans;
}

bool DFS(int x)
{
    Viz[x]=1;
    if(x==d)
        return Match[x]==0;
    if(x>n)
        return DFS(Match[x]);

    int i,y;

    for(i=0;i<D[x];++i)
    {
        y=G[x][i];
        if(!Viz[y] && Dm[y]==Dm[x]+1 && DFS(y))
        {
            Match[x]=y;
            Match[y]=x;
            return 1;
        }
    }
    return 0;
}

void solve()
{
    int i,j,ans=0;

    for(i=1;i<=n<<1;++i)
    {
        G[i]=(int*)malloc(D[i]*sizeof(int));
        D[i]=0;
    }
    for(i=0;i<m;++i)
    {
        G[X[i]][D[X[i]]++]=Y[i];
        G[Y[i]][D[Y[i]]++]=X[i];
    }

    for(i=1;i<=n;++i)
        for(j=0;j<D[i];++j)
            if(!Match[G[i][j]])
            {
                Match[i]=G[i][j];
                Match[G[i][j]]=i;
                ++ans;
                break;
            }

    while(d=BFS())
    {
        memset(Viz+1,0,(n<<1)*sizeof(bool));
        for(i=1;i<=n;++i)
            if(!Viz[i] && DFS(i))
                ++ans;
    }

    freopen("felinare.out","w",stdout);
    printf("%d\n",(n<<1)-ans);
    for(i=0;i<m;++i)
    {
        ans=0;
        if(Dm[X[i]])
            ans|=1;
        if(!Dm[Y[i]])
            ans|=2;
        printf("%d\n",ans);
    }
}
    
int main()
{
    read();
    solve();
    return 0;
}