#include <queue>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cassert>
#include <functional>
const int N = 1e3, M = N * N; std::bitset<N> f[N]; int ok[N], ook[N], del[N];
struct edge{ int v, nxt, c; }E[M]; int p[N], cnt = 1, vis[N][N], id[N][N]; 
void insert(int u, int v, int c) { E[++cnt].v = v; E[cnt].c = c; E[cnt].nxt = p[u]; p[u] = cnt; }
void addedge(int u, int v, int c) { insert(u, v, c); insert(v, u, 0); }
int d[N], cur[N], in[N], now[N], s, t; std::vector<int> lk[N];
bool bfs()
{
	for (int i = s; i <= t; ++i) d[i] = -1;
	std::queue<int> q; q.push(s); d[s] = 0; cur[s] = p[s];
	while (!q.empty())
	{
		int u = q.front(); q.pop(); 
		for (int i = p[u], v; i; i = E[i].nxt)
		{
			v = E[i].v; cur[v] = p[v]; 
			if (d[v] == -1 && E[i].c) d[v] = d[u] + 1, q.push(v);
		}
	}
	return (d[t] != -1);
}
int dfs(int u, int flow)
{
	if (u == t) return flow;
	int ans = 0, ret;
	for (int& i = cur[u], v; i; i = E[i].nxt)
	{
		v = E[i].v;
		if (E[i].c && d[v] == d[u] + 1)
		{
			ret = dfs(v, std::min(flow, E[i].c));
			flow -= ret; ans += ret;
			E[i].c -= ret; E[i ^ 1].c += ret;
			if (!flow) break;
		}
	}
	if (!ans) d[u] = -1;
	return ans;
}
int dinic() { int ans = 0; while (bfs()) ans += dfs(s, 2e9); return ans; }
int main()
{
	int n, m; scanf("%d%d", &n, &m);
	for (int i = 1, x, y; i <= m; ++i) scanf("%d%d", &x, &y), f[x][y] = 1;
	for (int k = 1; k <= n; ++k)
		for (int i = 1; i <= n; ++i) if (f[i][k]) f[i] |= f[k];
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j) 
			if (f[i][j]) addedge(i, j + n, 1), id[i][j] = cnt - 1;
	s = 0; t = n + n + 1; 
	for (int i = 1; i <= n; ++i) addedge(s, i, 1), addedge(i + n, t, 1);
	int ans = dinic(); printf("%d\n", n - ans);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			if (f[i][j] && !E[id[i][j]].c) vis[i][j] = 1;
	std::function<void(int, int)> dfs = [&](int u, int c)
	{
		in[u] = 1; lk[c].push_back(u);
		for (int i = 1; i <= n; ++i) if (vis[u][i] && !in[i]) dfs(i, c);
	}; int o = 0;
	for (int i = 1; i <= n; ++i) if (!in[i]) dfs(i, ++o);
	assert(n - ans == o);
	while (true)
	{
		std::bitset<N> nxt;
		for (int i = 1; i <= o; ++i) nxt |= f[lk[i][now[i]]];
		int flg = 0;
		for (int i = 1; i <= o; ++i) if (nxt[lk[i][now[i]]]) ++now[i], flg = 1;
		if (!flg) break;
	}
	for (int i = 1; i <= o; ++i) ok[lk[i][now[i]]] = 1;
	for (int i = 1; i <= n; ++i) printf("%d", ok[i]);
	puts("");
	for (int u = 1; u <= n; ++u)
	{
		for (int j = s; j <= t; ++j) p[j] = 0;
		for (int i = 1; i <= n; ++i) del[i] = 0;
		cnt = del[u] = 1; int tot = n - 1;
		for (int i = 1; i <= n; ++i) if (f[u][i] || f[i][u]) del[i] = 1, --tot;
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j)
				if (!del[i] && !del[j] && f[i][j]) addedge(i, j + n, 1);
		for (int i = 1; i <= n; ++i) addedge(s, i, 1);
		for (int i = 1; i <= n; ++i) addedge(i + n, t, 1);
		if (tot - dinic() == n - ans - 1) ook[u] = 1;
	}
	for (int i = 1; i <= n; ++i) printf("%d", ook[i]);
	puts(""); return 0;
}

我吐了。搜出来的路径覆盖和网络流跑出来的不一样，但网络流过掉了板子题。求调。