#include <bits/stdc++.h>

using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");
set<pair<int,pair<int,bool> > >s;
set<pair<int,pair<int,bool> > >::iterator it;
int hm[2][8200];
bool del[2][8200];
vector<int>nod[2][8200];
int n,m,x,y,ans;
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        nod[0][x].push_back(y);
        nod[1][y].push_back(x);
        hm[0][x]++;
        hm[1][y]++;
    }
    for(int i=1;i<=n;i++)
        for(int j=0;j<=1;j++)
            if(hm[j][i]>0)
                s.insert({hm[j][i],{i,j}});
    ans=n*2;
    while(!s.empty())
    {
        ans--;
        it=s.end();
        it--;
        int pos=it->second.first;
        bool j=it->second.second;
        del[j][pos]=true;
        s.erase(it);
        for(int i=0;i<nod[j][pos].size();i++)
            if(!del[1-j][nod[j][pos][i]])
            {
                it=s.find({hm[1-j][nod[j][pos][i]],{nod[j][pos][i],1-j}});
                s.erase(it);
                hm[1-j][nod[j][pos][i]]--;
                if(hm[1-j][nod[j][pos][i]]>0)
                    s.insert({hm[1-j][nod[j][pos][i]],{nod[j][pos][i],1-j}});
            }
    }
    fout<<ans<<"\n";
    for(int i=1;i<=n;i++)
    {
        int rez=0;
        for(int j=0;j<=1;j++)
            if(!del[j][i])
                rez+=(1<<j);
        fout<<rez<<"\n";
    }
    return 0;
}