#include<cstdio>
#include<vector>
#include<cstring>
#define MAXN 9000
using namespace std;
int left[MAXN],right[MAXN],left_pair[MAXN],right_pair[MAXN],seen[MAXN],answer=0;
vector<int> g[MAXN];
int match(int node){
    int i,dim=g[node].size();
    seen[node]=1;
    for(i=0;i<dim;i++)
        if(left_pair[g[node][i]]==0){
            answer++;
            left_pair[g[node][i]]=node;
            right_pair[node]=g[node][i];
            left[node]=1;
            return 1;
        }
    for(i=0;i<dim;i++)
        if(seen[left_pair[g[node][i]]]==0)
            if(match(left_pair[g[node][i]])==1){
                left_pair[g[node][i]]=node;
                left[node]=1;
                right_pair[node]=g[node][i];
                return 1;
            }
    return 0;
}
void support(int node){
    int i;
    for(i=0;i<g[node].size();i++)
        if(right[g[node][i]]==0){
            right[g[node][i]]=1;
            left[left_pair[g[node][i]]]=0;
            support(left_pair[g[node][i]]);
        }
}
int main(){
    freopen("felinare.in","r",stdin);
    freopen("felinare.out","w",stdout);
    int n,m,i,a,b,ok=1;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        g[a].push_back(b);
    }
    while(ok==1){
        ok=0;
        memset(seen,0,sizeof(seen));
        for(i=1;i<=n;i++)
            if(right_pair[i]==0&&match(i)==1)
                ok=1;
    }
    for(i=1;i<=n;i++)
        if(left[i]==0)
            support(i);
    printf("%d\n",2*n-answer);
    for(i=1;i<=n;i++)
        printf("%d\n",1-left[i]+2*(1-right[i]));
    return 0;
}