#include <fstream>
#include <cstring>
#include <queue>
#include <vector>
#define nmax 20005
#define inf 1e9
using namespace std;
ifstream cin("felinare.in");
ofstream cout("felinare.out");
int n,m,s,d,x,y,dist[nmax],mincut,nr;
struct edge{
    int flow,c;
};
vector<edge>mch;
struct elem{
    int x,id,idr;
};
vector<elem>v[nmax];
queue<int>q;
bool bfs(int s,int d){
    for(int i=0;i<=2*n+1;i++)
        dist[i]=inf;
    dist[s]=0;
    q.push(s);
    while(!q.empty()){
        int nod=q.front();
        q.pop();
        for(auto i:v[nod])
            if(dist[i.x]>dist[nod]+1&&mch[i.id].flow<mch[i.id].c){
                dist[i.x]=dist[nod]+1;
                q.push(i.x);
            }
    }
    return dist[d]!=inf;
}
int dinic(int nod,int d,int val){
    if(val==0)
        return 0;
    if(nod==d)
        return val;
    int total=0;
    for(auto i:v[nod])
        if(dist[i.x]==dist[nod]+1&&mch[i.id].flow<mch[i.id].c){
            int add=dinic(i.x,d,min(val-total,mch[i.id].c-mch[i.id].flow));
            mch[i.id].flow+=add;
            mch[i.idr].flow-=add;
            total+=add;
        }
    return total;
}
void add_edge(int x,int y){
    mch.push_back({0,1});
    v[x].push_back({y,nr,nr+1});
    nr++;
    mch.push_back({0,0});
    v[y].push_back({x,nr,nr-1});
    nr++;
}
int solve(int i){
    int ans=0;
    if(dist[i]!=inf)
        ans|=1;
    if(dist[i+n]==inf)
        ans|=2;
    return ans;
}
signed main()
{
    cin>>n>>m;
    d=2*n+1;
    for(int i=1;i<=n;i++){
        add_edge(0,i);
        add_edge(i+n,d);
    }
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        add_edge(x,y+n);
    }
    while(bfs(0,d))
        mincut+=dinic(0,d,inf);
    cout<<2*n-mincut<<'\n';
    for(int i=1;i<=n;i++)
        cout<<solve(i)<<'\n';
    return 0;
}