#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int n, m, k, tot, cnt;
int head[N], nxt[N << 1], to[N << 1];
int dis[N];
vector<int> a[N];
bool ans[N];
vector<int> ans1[N];
void add(int u, int v) {
  nxt[++tot] = head[u];
  head[u] = tot;
  to[tot] = v;
}
void bfs(int x) {
  dis[x] = 1;
  queue<int> Q;
  Q.push(x);
  while (!Q.empty()) {
    int k = Q.front();
    Q.pop();
    for (int i = head[k]; i; i = nxt[i]) {
      int p = to[i];
      if (dis[p]) continue;
      dis[p] = dis[k] + 1;
      Q.push(p);
    }
  }
}
void dfs(int x) {
  if (cnt == k) return;
  if (x > n) {
    cnt += 1;
    for (int i = 1; i <= m; ++i) ans1[i].push_back(ans[i]);
    return;
  }
  for (int i = 0; i <= a[x].size() - 1; ++i)
    ans[a[x][i]] = 1, dfs(x + 1), ans[a[x][i]] = 0;
}
int main() {
  n = read();
  m = read();
  k = read();
  for (int i = 1; i <= m; ++i) {
    int u = read(), v = read();
    add(u, v);
    add(v, u);
  }
  bfs(1);
  for (int i = 1; i <= n; ++i)
    for (int j = head[i]; j; j = nxt[j]) {
      int p = to[j];
      if (dis[i] + 1 != dis[p]) continue;
      a[p].push_back((j + 1) / 2);
    }
  dfs(2);
  printf("%d\n", cnt);
  for (int i = 0; i <= ans1[1].size() - 1; ++i) {
    for (int j = 1; j <= m; ++j) printf("%d", (int)ans1[j][i]);
    printf("\n");
  }
  return 0;
}
