#include <cstdio>
#include <algorithm>
#include <bitset>

namespace Dinic {
	const int Inf = 0x3f3f3f3f;
	const int MN = 205, MM = 5155;
	
	int N, S, T;
	int h[MN], iter[MN], nxt[MM * 2], to[MM * 2], w[MM * 2], tot;
	
	inline void Init(int _N) {
		N = _N, tot = 1;
		for (int i = 1; i <= N; ++i) h[i] = 0;
	}
	inline void SetST(int _S, int _T) { S = _S, T = _T; }
	
	inline void ins(int u, int v, int x) { nxt[++tot] = h[u], to[tot] = v, w[tot] = x, h[u] = tot; }
	inline void insw(int u, int v, int w1 = Inf, int w2 = 0) {
		if (!u) u = S; if (!v) v = T;
		ins(u, v, w1), ins(v, u, w2);
	}
	
	int lv[MN], que[MN], l, r;
	
	inline bool Lvl() {
		for (int i = 1; i <= N; ++i) lv[i] = 0;
		lv[S] = 1;
		que[l = r = 1] = S;
		while (l <= r) {
			int u = que[l++];
			for (int i = h[u]; i; i = nxt[i])
				if (w[i] && !lv[to[i]]) {
					lv[to[i]] = lv[u] + 1;
					que[++r] = to[i];
				}
		}
		return lv[T] != 0;
	}
	
	int Flow(int u, int f) {
		if (u == T) return f;
		int d = 0, s = 0;
		for (int &i = iter[u]; i; i = nxt[i])
			if (w[i] && lv[to[i]] == lv[u] + 1) {
				d = Flow(to[i], std::min(f, w[i]));
				f -= d, s += d;
				w[i] -= d, w[i ^ 1] += d;
				if (!f) break;
			}
		return s;
	}
	
	inline int DoDinic() {
		int Ans = 0;
		while (Lvl()) {
			for (int i = 1; i <= N; ++i) iter[i] = h[i];
			Ans += Flow(S, Inf);
		}
		return Ans;
	}
}
using Dinic::Init;
using Dinic::SetST;
using Dinic::insw;
using Dinic::DoDinic;
using Dinic::h;
using Dinic::nxt;
using Dinic::to;
using Dinic::w;

const int MN = 105;

int N, M, Ans;
std::bitset<101> g[MN];

int match[MN], tagl[MN], tagr[MN];
void DFS(int u) {
	tagr[u] = 1;
	for (int i = 1; i <= N; ++i)
		if (g[i][u] && !tagl[i])
			tagl[i] = 1, DFS(match[i]);
}

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= M; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		g[x][y] = 1;
	}
	for (int k = 1; k <= N; ++k)
		for (int i = 1; i <= N; ++i)
			if (g[i][k]) g[i] |= g[k];
	Init(N + N + 2), SetST(N + N + 1, N + N + 2);
	for (int i = 1; i <= N; ++i)
		insw(0, i, 1), insw(N + i, 0, 1);
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j)
			if (g[i][j]) insw(i, N + j, 1);
	Ans = N - DoDinic();
	printf("%d\n", Ans);
	for (int i = 1; i <= N; ++i) if (!w[4 * i - 2]) {
		for (int j = h[i]; j; j = nxt[j])
			if (!w[j]) { match[i] = to[j] - N; break; }
	}
	for (int i = 1; i <= N; ++i) if (w[4 * i]) DFS(i);
	for (int i = 1; i <= N; ++i) printf("%d", !tagl[i] && tagr[i]);
	puts("");
	for (int u = 1; u <= N; ++u) {
		static int del[MN]; int cnt = 0;
		for (int i = 1; i <= N; ++i) del[i] = i == u || g[i][u] || g[u][i];
		Init(N + N + 2), SetST(N + N + 1, N + N + 2);
		for (int i = 1; i <= N; ++i) if (!del[i])
			insw(0, i, 1), insw(N + i, 0, 1), ++cnt;
		for (int i = 1; i <= N; ++i) if (!del[i])
			for (int j = 1; j <= N; ++j) if (!del[j])
				if (g[i][j]) insw(i, N + j, 1);
		printf("%d", cnt - DoDinic() == Ans - 1);
	} puts("");
	return 0;
}