#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
const int N=1e3+1,M=1e4+1,inf=1e9;
int n,m,s,t,tot,ans;
int h[N],h2[N],dep[N],in[N];
bool f[N],vis[N][N];
struct Edge{
	int to,nxt,cap,flow;
}e[M*2];
void add(int u,int v,int w){
	e[tot].to=v,e[tot].nxt=h[u],e[tot].cap=w;
	h[u]=tot++;
	e[tot].to=u,e[tot].nxt=h[v];
	h[v]=tot++;
}
int bfs(){
	queue<int>q;
	q.push(s),memset(dep,0,sizeof(dep)),dep[s]=1;
	while(q.size()){
		int u=q.front();
		q.pop();
		for(int i=h[u];~i;i=e[i].nxt){
			int v=e[i].to;
			if(!dep[v]&&e[i].cap>e[i].flow)
				dep[v]=dep[u]+1,q.push(v);
		}
	}
	return dep[t];
}
int dfs(int u,int flow){
	if(u==t||!flow)
		return flow;
	int sum=0;
	for(int& i=h2[u];~i;i=e[i].nxt){
		int v=e[i].to,d;
		if(dep[v]==dep[u]+1){
			d=dfs(v,min(flow-sum,e[i].cap-e[i].flow));
			sum+=d,e[i].flow+=d,e[i^1].flow-=d;
			if(sum==flow)
				break;
		}
	}
	return sum;
}
void dfs_(int u){
	f[u]=1;
	for(int i=h[u];~i;i=e[i].nxt){
		int v=e[i].to;
		if(v==s||v==t||f[v])
			continue;
		if(u>n){
			if(!e[i^1].flow)
				dfs_(v);
		}
		else{
			if(e[i].flow)
				dfs_(v);
		}
	}
}
signed main(){
	n=read(),m=read();
	t=2*n+1;
	memset(h,-1,sizeof(h));
	for(int i=1;i<=n;i++)
		add(s,i,1),add(i+n,t,1);
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		vis[u][v]=1;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++)
				if(vis[i][j]&&vis[j][k])
					vis[i][k]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(vis[i][j])
				add(i,j+n,1);
	while(bfs()){
		memcpy(h2,h,sizeof(h));
		ans+=dfs(s,inf);
	}
	write(ans),putchar('\n');
	for(int i=1+n;i<=n*2;i++)
		for(int j=h[i];~j;j=e[j].nxt){
			if(e[j].flow&&!f[i])
				dfs_(i);
		}
	for(int i=1;i<=n;i++)
		write(f[i]&&!f[i+n]);
	putchar('\n');
	for(int i=1;i<=n;i++){
		int tmp=n;
		for(int j=0;j<tot;j++)
			e[j].flow=0;
		for(int j=1;j<=n;j++)
			if(vis[i][j]||vis[j][i]||i==j){
				tmp--;
				for(int k=h[j];~k;k=e[k].nxt)
					e[k].flow=e[k].cap,e[k^1].flow=e[k^1].cap;
				for(int k=h[j+n];~k;k=e[k].nxt)
					e[k].flow=e[k].cap,e[k^1].flow=e[k^1].cap;
			}
		int sum=0;
		while(bfs()){
			memcpy(h2,h,sizeof(h));
			sum+=dfs(s,inf);
		}
		write(tmp-sum==ans-1);
	}
	return 0;
}