#include <bits/stdc++.h>
using namespace std;
inline int rd() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
struct Edge {
  int u, v, next;
} e[400005];
int head[400005], cnt = 1;
inline void addedge(int u, int v) {
  e[++cnt].u = u;
  e[cnt].v = v;
  e[cnt].next = head[u];
  head[u] = cnt;
}
int d[400005], n, m, k;
long long ans = 1;
queue<int> q;
vector<int> rc[400005];
int use[400005], num = 0, p[400005];
bool cmp(int a, int b) { return d[a] < d[b]; }
void solve(int t) {
  if (num == ans) return;
  if (t == n + 1) {
    for (int i = 1; i <= m; i++) printf("%d", use[i]);
    printf("\n");
    num++;
    return;
  }
  for (int i = 0; i < rc[p[t]].size(); i++) {
    use[rc[p[t]][i]] = 1;
    solve(t + 1);
    use[rc[p[t]][i]] = 0;
  }
}
int main() {
  n = rd(), m = rd(), k = rd();
  for (int i = 1; i <= m; i++) {
    int x = rd(), y = rd();
    addedge(x, y);
    addedge(y, x);
  }
  memset(d, 0x3f, sizeof(d));
  q.push(1);
  d[1] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; i; i = e[i].next) {
      int v = e[i].v;
      if (d[v] == 0x3f3f3f3f) {
        d[v] = d[u] + 1;
        q.push(v);
      }
    }
  }
  for (int i = 1; i <= n; i++) p[i] = i;
  sort(p + 1, p + n + 1);
  for (int i = 1; i <= n; i++) {
    for (int j = head[i]; j; j = e[j].next) {
      if (d[i] + 1 == d[e[j].v]) {
        rc[e[j].v].push_back(j / 2);
      }
    }
  }
  for (int i = 2; i <= n; i++) {
    ans = ans * rc[p[i]].size();
    if (ans >= k) {
      break;
    }
  }
  ans = min(ans, 1ll * k);
  cout << ans << endl;
  solve(2);
}
