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;
	    return 1;
	}

    for(it=a[n].begin(); it!=a[n].end(); ++it)
	if(pairup(l[*it]))
	{
	    l[*it]=n;
	    r[n]=*it;
	    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;
    }

}


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[i]=0;

    for(i=1;i<=n;++i) 
    {
	if(sl[i]==-1) sl[i]=1;
	if(sr[i]==-1) sr[i]=1;
    }

    printf("%d\n", 2*n-flow);
    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;
}