#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

const int MAX_N=9010;

vector<int> A[MAX_N];
vector<int> B[MAX_N];

int st[MAX_N];
int dr[MAX_N];
int viz[MAX_N];

bool pairup(int nod) {
    if(viz[nod]) {
        return false;
    }
    viz[nod]=1;

    for(vector<int>::iterator it=A[nod].begin(); it!=A[nod].end(); it++) {
        if(!dr[*it]) {
            st[nod]=*it;
            dr[*it]=nod;
            return true;
        }
    }

    for(vector<int>::iterator it=A[nod].begin(); it!=A[nod].end();it++) {
        if(pairup(dr[*it])) {
            st[nod]=*it;
            dr[*it]=nod;
            return true;
        }
    }
    return false;
}

vector<int> cuplaj(int n) {
    bool change=true;
    while(change) {
        change=false;
        memset(viz,0,sizeof(viz));
        for(int i=1;i<=n;i++) {
            if(!st[i]) {
                if(pairup(i)) {
                    change=true;
                }
            }
        }
    }
    
    memset(dr,0,sizeof(dr));
    vector<int> c;
    for(int i=1;i<=n;i++) {
        if(st[i]) {
            dr[st[i]]=i;
            c.push_back(i);
        }
    }
    return c;
}

int L[MAX_N];
int R[MAX_N];

bool vecin(int nod) {
    for(vector<int>::iterator it=B[nod].begin(); it!=B[nod].end(); it++) {
        if(!st[*it]) {
            return true;
        }
    }
    return false;
}

void misca(int nod) {
    for(vector<int>::iterator it=A[nod].begin();it++) {
        if(!R[*it]) {
            R[*it]=2;
            L[dr[*it]]=0;
            misca(dr[*it]);
        }
    }
}

int main() {
    freopen("felinare.in","r",stdin);
    freopen("felinare.out","w",stdout);
    
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) {
        int a,b;
        scanf("%d%d",&a,&b);
        A[a].push_back(b);
        B[b].push_back(a);
    }
    

    vector<int>c=cuplaj(n);
    printf("%d\n",2*n-c.size());
    for(vector<int>::iterator it=c.begin(); it!=c.end(); it++) {
        sol[*it]--;
        L[*it]=1;
    }

    for(int i=1;i<=n;i++) {
        if(!L[i]) {
            misca(i);
        }
    }
    
    for(int i=1;i<=n;i++) {
        printf("%d\n",sol[i]);
    }
    
    return 0;
}