#include <cstdio>
#include <vector>
#include <cstring>

#define SIZE 8193
using namespace std;

int n, m, MAX, left[SIZE], right[SIZE];
bool visited[SIZE], in_sup_r[SIZE], in_sup_l[SIZE];
vector <int> adj[SIZE];

inline void read();
inline void write();
inline void solve();

int main()
{
    read();
    solve();
    write();
    return 0;
}

inline void read()
{
    freopen("felinare.in", "r", stdin);

    scanf("%d%d", &n, &m);

    while( m-- )
    {
        int x, y;

        scanf("%d%d", &x, &y);
        adj[ x ].push_back( y );
    }
}

inline bool couple(int node )
{
    if( visited[node] )
        return 0;
    visited[node] = 1;

    for( vector <int> :: iterator it = adj[node].begin(); it != adj[node].end(); ++it)
        if( ! left[*it] )
        {
            left[ *it ] = node;
            right[ node ] = *it;

            return 1;
        }
        else if ( couple( left [ *it ] ) )
        {
            left[ *it ] = node;
            right[ node ] = *it;

            return 1;
        }

    return 0;
}

inline void support( int node )
{
    for( vector <int> :: iterator it = adj[ node ].begin(); it != adj[node].end(); ++it)
        if( ! in_sup_r[ *it ])
        {
            in_sup_r[ *it ] = 1;
            in_sup_l[ left[ *it ] ] = 0;
            support( left[ *it ]);
        }
}

inline void solve()
{
    bool sw = 1;
    while( sw )
    {
        memset(visited, 0, sizeof(visited));
        sw = 0;
        for(int i = 1; i <= n; ++i)
            if( !right[i] && couple(i))
            {
                sw = 1;
                ++MAX;
            }
    }

    for(int i = 1; i <= n; ++i)
        if( right[ i ] )
            in_sup_l[ i ] = 1;

    for(int i = 1; i <= n; ++i)
        if( ! in_sup_l[ i ] )
            support( i );
}

inline void write()
{
    freopen("felinare.out", "w", stdout);
    printf("%d\n", 2 * n - MAX);
    for(int i = 1; i <= n; ++i)
        if( in_sup_l[i] && in_sup_r[i])
            printf("0\n");
        else if( !in_sup_l[i] && in_sup_r[i])
            printf("1\n");
        else if( !in_sup_l[i] && !in_sup_r[i])
            printf("3\n");
        else
            printf("2\n");
}