#include <bits/stdc++.h>
using namespace std;
int n, m, k, hed[200050], cnt;
struct EG {
  int to, id, nxt;
} e[2 * 200050];
void ae(int f, int t, int v) {
  e[++cnt].to = t;
  e[cnt].id = v;
  e[cnt].nxt = hed[f];
  hed[f] = cnt;
}
int dep[200050];
bool vis[200050];
void dij() {
  memset(dep, 0x3f, sizeof(dep));
  dep[1] = 0;
  queue<int> q;
  q.push(1);
  vis[1] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int j = hed[u]; j; j = e[j].nxt) {
      int to = e[j].to;
      if (!vis[to]) {
        vis[to] = 1;
        dep[to] = dep[u] + 1;
        q.push(to);
      }
    }
  }
}
int f[200050];
int ans[200050], sum = 1;
void dfs(int i) {
  if (i == n + 1) {
    for (int i = 1; i <= m; i++) printf("%d", ans[i]);
    printf("\n");
    sum--;
    if (!sum) exit(0);
  }
  for (int j = hed[i]; j; j = e[j].nxt) {
    int to = e[j].to;
    if (dep[to] != dep[i] - 1) continue;
    ans[e[j].id] = 1;
    dfs(i + 1);
    ans[e[j].id] = 0;
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int f, t, i = 1; i <= m; i++) {
    scanf("%d%d", &f, &t);
    ae(f, t, i), ae(t, f, i);
  }
  dij();
  for (int i = 2; i <= n; i++) {
    int cnt = 0;
    for (int j = hed[i]; j; j = e[j].nxt) {
      int to = e[j].to;
      if (dep[to] == dep[i] - 1) cnt++;
    }
    sum *= cnt;
    if (sum >= k) {
      sum = k;
      break;
    }
  }
  printf("%d\n", sum);
  dfs(2);
  return 0;
}
