#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') {
      f = -1;
    }
    c = getchar();
  }
  while (c <= '9' && c >= '0') {
    x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  }
  return x * f;
}
const long long INF = 0x3f3f3f3f3f3f3f3f;
const long long Maxn = 3e5 + 5;
const long long Maxm = 6e5 + 5;
long long n, m, s, k, cnt, sum, tot = 1, head[Maxn], dis[Maxn], pre[Maxn];
bool vis[Maxn];
struct Line {
  long long to;
  long long next;
  long long num;
} edges[Maxm];
inline void Add(long long a, long long b, long long w) {
  ++cnt;
  edges[cnt].to = b;
  edges[cnt].next = head[a];
  edges[cnt].num = w;
  head[a] = cnt;
  return;
}
vector<long long> v[Maxn];
void BFS(long long start) {
  queue<long long> q;
  q.push(start);
  dis[start] = 0;
  while (!q.empty()) {
    long long u = q.front();
    q.pop();
    for (register long long i = head[u]; i != 0; i = edges[i].next) {
      long long next = edges[i].to, num = edges[i].num;
      if (!dis[next]) {
        dis[next] = dis[u] + 1;
        v[next].push_back(num);
        q.push(next);
      } else if (dis[next] == dis[u] + 1) {
        v[next].push_back(num);
      }
    }
  }
}
void DFS(long long x) {
  if (x == n + 1) {
    for (register long long i = 1; i <= m; ++i) {
      printf("%d", vis[i]);
    }
    puts("");
    sum++;
    if (sum == tot) {
      exit(0);
    }
    return;
  }
  for (register long long i = 0; i < v[x].size(); ++i) {
    vis[v[x][i]] = 1;
    DFS(x + 1);
    vis[v[x][i]] = 0;
  }
  return;
}
signed main() {
  n = read(), m = read(), k = read();
  for (register long long i = 1; i <= m; ++i) {
    long long x = read(), y = read();
    Add(x, y, i), Add(y, x, i);
  }
  BFS(1);
  for (register long long i = 2; i <= n; ++i) {
    if (tot * v[i].size() > k) {
      tot = k;
      break;
    } else {
      tot *= v[i].size();
    }
  }
  printf("%d\n", tot);
  DFS(2);
  return 0;
}
