// sursa inspiratie -> https://infoarena.ro/job_detail/3312475?action=view-source
#include <bits/stdc++.h>
#define VMAX 20007
#define NMAX 105
#define INF 1e16+1
#define int long long int
using namespace std;
ifstream fin ("felinare.in");
ofstream fout ("felinare.out");

vector<int> graf_total[VMAX];
vector<int> graf[VMAX]; // nod si id
bool stins[2*VMAX];
int nod_cu_care_e_cuplat[2][VMAX];
bool vizitat[VMAX];

vector<pair<int,int>> muchii_cuplate;



bool cuplaj(int nod)
{
    if(vizitat[nod])
        return 0;
    vizitat[nod]=1;

    //cautam o muchie goala
    for(auto it:graf[nod])
    {
        if(nod_cu_care_e_cuplat[1][it]==0) // cuplam
        {
            nod_cu_care_e_cuplat[0][nod]=it;
            nod_cu_care_e_cuplat[1][it]=nod;
            return 1;
        }
    }

    //cautam un drum luat si incercam sa marim drumul pe unul dintre acestea
    for(auto it:graf[nod])
    {
        if(nod_cu_care_e_cuplat[1][it])
        {
            //int nr = cuplaj(nod_cu_care_e_cuplat[1][it]) // cautam o cuplare mai buna in care it e conectat cu nod de fapt
            if(cuplaj(nod_cu_care_e_cuplat[1][it])) // daca am gasit solutie mai buna
            {
                nod_cu_care_e_cuplat[1][it]=nod;
                nod_cu_care_e_cuplat[0][nod]=it;
                return 1;
            }
        }
    }

    return 0;


}
vector<int> numere;
pair<int,int> range_duplicati[NMAX];
vector<pair<int,int>> divi_nr[NMAX];
set<int> divizori_posibili;

vector<pair<int,int>> divizori(int nr)
{
    int i;
    vector<pair<int,int>> divii;
    for(i=2;i*i<=nr;i++)
    {
        if(nr%i==0)
        {
            divii.push_back({i,0});
            divizori_posibili.insert(i);
            while(nr%i==0)
            {
                divii.back().second++;
                nr/=i;
            }
        }
    }

    if(nr!=1)
    {
        divii.push_back({nr,1});
        divizori_posibili.insert(nr);
    }
    return divii;

}


int get_cuplaj(int n)
{
    int i,j,k,nr;
    bool modificare=1;

    while(modificare)
    {
        modificare=0;
        for(i=1;i<=n;i++)
            vizitat[i]=0;
        for(i=1;i<=n;i++)
            if(nod_cu_care_e_cuplat[0][i]==0 && cuplaj(i))
                modificare = 1;
    }


    for(i=1;i<=n;i++)
    {
        if(nod_cu_care_e_cuplat[0][i])
        {
            muchii_cuplate.push_back({i,nod_cu_care_e_cuplat[0][i]});
            cout<<muchii_cuplate.back().first<<' '<<muchii_cuplate.back().second<<'\n';
            stins[i]=1;
        }

    }

    nr=muchii_cuplate.size();
    //for(i=0;i<=n;i++)
     //   nod_cu_care_e_cuplat[0][i]=nod_cu_care_e_cuplat[1][i]=0;

    return nr;
}


signed main()
{
    ios_base::sync_with_stdio(0);
    int n,m,i,j,k,t,q,nr,lg,nod,minim,maxim,suma,st,dr,mij,ramase,ult_min,loc_ram;
    fin>>n>>m;

    for(i=0;i<m;i++)
    {
        fin>>j>>k;
        graf[j+n].push_back(k);
    }

    suma=get_cuplaj(2*n);

    fout<<2*n-suma<<'\n';
    for(i=1;i<=n;i++)
    {
        fout<<(stins[i]==0)+(stins[i+n]==0)*2<<'\n';
    }






    return 0;
}