#include <bits/stdc++.h>
using namespace std;
const long long N = 2e5 + 5;
inline long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + (ch ^ 48);
    ch = getchar();
  }
  return x * f;
}
long long n, m, k;
long long head[N], cnt;
struct Edge {
  long long to, nxt;
} e[N << 1];
inline void add(long long u, long long v) {
  e[++cnt].nxt = head[u];
  e[cnt].to = v;
  head[u] = cnt;
}
long long dis[N];
vector<long long> S[N];
bool vis[N];
long long tot = 1;
inline void bfs(long long s) {
  queue<long long> q;
  memset(dis, 0x3f, sizeof(dis));
  dis[s] = 0;
  q.push(s);
  while (!q.empty()) {
    long long u = q.front();
    q.pop();
    if (vis[u]) continue;
    vis[u] = true;
    for (register long long i = head[u]; i; i = e[i].nxt) {
      long long v = e[i].to;
      if (dis[v] >= dis[u] + 1) {
        dis[v] = dis[u] + 1;
        S[v].push_back(i);
        q.push(v);
      }
    }
  }
}
long long res;
void dfs(long long step) {
  if (step == n + 1) {
    for (register long long i = 1; i <= m; i++) printf("%d", vis[i]);
    puts("");
    res++;
    if (res >= k) exit(0);
    return;
  }
  for (register long long i = 0; i < S[step].size(); i++) {
    vis[(S[step][i] + 1) / 2] = 1;
    dfs(step + 1);
    vis[(S[step][i] + 1) / 2] = 0;
  }
}
signed main() {
  n = read(), m = read(), k = read();
  for (register long long i = 1; i <= m; i++) {
    long long u = read(), v = read();
    add(u, v), add(v, u);
  }
  bfs(1);
  memset(vis, 0, sizeof(vis));
  bool flag = true;
  for (register long long i = 2; i <= n; i++) {
    tot *= S[i].size();
    if (tot >= k) {
      flag = false;
      break;
    }
  }
  printf("%lld\n", flag ? tot : k);
  dfs(2);
  return 0;
}
