using namespace std;
#include <cstdio>
#include <vector>
#define maxn 8201

vector<int> a[maxn];
int n, m;
int l[maxn], r[maxn],sl[maxn], sr[maxn];
bool use[maxn];

void read()
{
    freopen("felinare.in","r",stdin);
    scanf("%d %d\n", &n, &m);
    int p, q;
    while(m--)
    {
	scanf("%d %d\n", &p, &q);
	a[p].push_back(q);
    }
}

inline bool pairup(int n)
{
    if(use[n])return 0;
    use[n]=1;

    vector<int>::iterator it;

    for(it=a[n].begin(); it!=a[n].end(); ++it)
	if(!l[*it])
	{
	    l[*it]=n;
	    r[n]=*it;
	    sl[n]=1;
	    return 1;
	}

    for(it=a[n].begin(); it!=a[n].end(); ++it)
	if(pairup(l[*it]))
	{
	    l[*it]=n;
	    r[n]=*it;
	    sl[n]=1;
	    return 1;
	}

    return 0;
}

void hopcroft_karp()
{
    int i, ok=1;

    while(ok)
    {
	ok=0;
	memset(use, 0, sizeof(bool)*(n+2));

	for(i=1;i<=n;++i)
	    if(!r[i])
		if(pairup(i)) ok=1;
    }

}

inline void support(int n)
{
    vector<int>::iterator it;

   // printf("(%d)\n",n);
    for(it=a[n].begin(); it!=a[n].end(); ++it)
	if(!sr[*it])
	{
	    sr[*it]=1;
	    sl[l[*it]]=0;
	    support(l[*it]);
	}
}


void solve()
{
    int i;
    hopcroft_karp();
    int flow=0;
    for(i=1;i<=n;++i) if(r[i]) ++flow;

    //for(i=1;i<=n;++i) sl[i]=sr[i]=-1;

   // for(i=1;i<=n;++i) if(r[i]) sl[i]=1, sr[r[i]]=0;


   // for(i=1;i<=n;++i) if(!sl[i]) support(i);   

    
//    for(i=1;i<=n;++i) printf("%d %d\n", sl[i], sr[i]);
    
    printf("%d\n", 2*n-flow);

	for(i=1;i<=n;++i) if(!l[i]) sl[i]=1;
	for(i=1;i<=n;++i) if(r[i]) sr[i]=1;
    for(i=1;i<=n;++i)
    {
	if(sl[i] && sr[i]) printf("0\n");
	if(!sl[i] && sr[i]) printf("1\n");
	if(sl[i] && !sr[i]) printf("2\n");
	if(!sl[i] && !sr[i]) printf("3\n");
    }


}

int main()
{
   freopen("felinare.out","w",stdout);
    read();
    solve();

    return 0;
}