#include <bits/stdc++.h>
using namespace std;
inline char getc() {
  static char buf[1 << 14], *p1 = buf, *p2 = buf;
  return (p1 == p2) &&
                 (p2 = (p1 = buf) + fread(buf, 1, 1 << 14, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline int scan() {
  register int x = 0;
  register char ch = 0;
  while (ch < 48) ch = getc();
  while (ch >= 48) x = x * 10 + ch - 48, ch = getc();
  return x;
}
const int N = 2e5 + 5;
int n, m, k, head[N], nex[N << 1], dis[N], cc;
struct Edge {
  int u, v, id;
  Edge(int c = 0, int a = 0, int b = 0) : u(c), v(a), id(b) {}
} E[N << 1];
inline void add(int u, int v, int id) {
  nex[++cc] = head[u];
  E[cc] = Edge(u, v, id);
  head[u] = cc;
}
queue<int> Q;
int he[N], _nex[N << 1], idx[N << 1];
inline void _add(int u, int id) {
  static int o = 0;
  _nex[++o] = he[u];
  idx[o] = id;
  he[u] = o;
}
string res[N];
int cnt;
char vis[N];
inline void dfs(int u) {
  if (cnt >= k) return;
  if (u == n + 1) {
    cnt++;
    for (register int i = 1; i <= m; i++) res[cnt] += vis[i];
    return;
  }
  for (int i = he[u]; i; i = _nex[i]) {
    vis[idx[i]] = '1';
    dfs(u + 1);
    vis[idx[i]] = '0';
  }
}
int main() {
  n = scan(), m = scan(), k = scan();
  for (register int i = 1; i <= m; i++) {
    int u = scan(), v = scan();
    add(u, v, i), add(v, u, i);
  }
  dis[1] = 0;
  Q.push(1);
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    for (int i = head[u]; i; i = nex[i]) {
      int v = E[i].v;
      if (v == 1 || dis[v]) continue;
      dis[v] = dis[u] + 1;
      Q.push(v);
    }
  }
  for (register int i = 1; i <= cc; i++) {
    int u = E[i].u, v = E[i].v;
    if (dis[u] + 1 == dis[v]) _add(v, E[i].id);
  }
  memset(vis, '0', sizeof(vis));
  dfs(2);
  printf("%d\n", cnt);
  for (register int i = 1; i <= cnt; i++) cout << res[i] << '\n';
  return 0;
}
