#include<bits/stdc++.h>

#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define sz size
#define pb push_back
#define mp make_pair
#define bg begin
#define nd end
using namespace std;

#define int long long

const int maxn = 100003;
const int maxk = 1003;

ifstream fin("felinare.in");
ofstream fout("felinare.out");

int n,m;
int x,y;

bitset<16400> sol;
bitset<8200> viz;

vector<int> g[8200];
int match[16400];

int pairup(int v){

	if(viz[v]) return 0;
	viz[v] = 1;
	for(int ch : g[v]){
		if(!match[ch] || pairup(match[ch])){
			match[ch] = v;
			match[v] = ch;
			return 1;
		}
	}
	return 0;
}

void solve(int v){

	sol[v] = 0;
	for(int ch : g[v]){
		if(!sol[ch]){
			sol[ch] = 1;
			solve(match[ch]);
		}
	}
}

int32_t main(){

	//#ifndef ONLINE_JUDGE
	//freopen("input.in","r",stdin);
	//#endif

	ios_base::sync_with_stdio(false);

	fin >> n >> m;
	for(int i=0;i<m;i++){
		fin >> x >> y;
		g[x].pb(y+n);
	}

	bool ok = true;
	while(ok){
		ok = false;
		viz&=0;
		for(int i=1;i<=n;i++){
			if(!match[i]) ok|=pairup(i);
		}
	}
	for(int i=1;i<=n;i++){
		if(match[i]) sol[i] = 1;
	}
	for(int i=1;i<=n;i++){
		if(!match[i]) solve(i);
	}
	int ans = 2*n;
	for(int i=1;i<=n;i++){
		ans = ans - sol[i];
	}
	fout << ans << '\n';
	for(int i=1;i<=n;i++){
		int frst = (!sol[i]);
		int sec =((!sol[i+n])<<1); 
		fout << (frst | sec) << '\n';
	}

	return 0;
}