#include <bits/stdc++.h>

using namespace std;

ifstream in("felinare.in");
ofstream out("felinare.out");

const int NMAX = 8197;

vector<int> g[2*NMAX];

int dp[2*NMAX][2];

int a[NMAX];
int b[NMAX];

int main()
{
    int n, m; in >> n >> m;

    for(int i = 0; i < m; i++)
    {
        int x, y; in >> x >> y;
        a[x]++;
        b[y]++;
    }

    int nr_only_in = 0;
    int nr_only_out = 0;
    for(int i = 1; i <= n; i++)
    {
        if(a[i] == 0) nr_only_out++;
        if(b[i] == 0) nr_only_in++;
    }

    if(nr_only_in > nr_only_out)
    {
        out << n + nr_only_in << "\n";
        for(int i = 1; i <= n; i++)
        {
            int mask = 1;
            if(b[i] == 0) mask |= 2;

            out << mask << "\n";
        }
    }
    else
    {
        out << n + nr_only_out << "\n";
        for(int i = 1; i <= n; i++)
        {
            int mask = 2;
            if(a[i] == 0) mask |= 1;

            out << mask << "\n";
        }
    }
}