#include <bits/stdc++.h>
using namespace std;
const long long maxn = 3e5 + 15;
const long long maxm = 1e6 + 15;
long long n, m, dis[maxn], hd[maxn], pre[maxn], cnt, x, y, w, val[maxm],
    ans = 1, k, num;
bool vis[maxm];
vector<long long> posi[maxn];
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;
}
struct Edge {
  long long nxt, to;
} edge[maxm];
void add(long long u, long long v) {
  edge[++cnt].nxt = hd[u];
  edge[cnt].to = v;
  hd[u] = cnt;
  return;
}
struct Node {
  long long dis, id;
  Node() {}
  Node(long long x, long long y) : dis(x), id(y) {}
  bool operator<(const Node& x) const { return dis > x.dis; }
};
priority_queue<Node> q;
void dij() {
  memset(dis, 0x3f, sizeof dis);
  dis[1] = 0;
  q.push(Node(0, 1));
  while (!q.empty()) {
    long long u = q.top().id;
    q.pop();
    if (vis[u]) continue;
    vis[u] = true;
    for (long long i = hd[u]; i; i = edge[i].nxt) {
      long long v = edge[i].to;
      if (dis[v] == dis[u] + 1) {
        posi[v].push_back(i);
      }
      if (dis[v] > dis[u] + 1) {
        dis[v] = dis[u] + 1;
        posi[v].clear();
        posi[v].push_back(i);
        q.push(Node(dis[v], v));
      }
    }
  }
  return;
}
void dfs(long long pos) {
  if (pos == n + 1) {
    num++;
    for (long long i = 1; i <= m; i++) {
      cout << vis[i];
    }
    cout << endl;
    if (num == ans) exit(0);
    return;
  }
  for (long long i = 0; i < posi[pos].size(); i++) {
    vis[posi[pos][i] / 2] = true;
    dfs(pos + 1);
    vis[posi[pos][i] / 2] = false;
  }
  return;
}
signed main() {
  n = read();
  m = read();
  k = read();
  cnt = 1;
  for (long long i = 1; i <= m; i++) {
    x = read();
    y = read();
    add(x, y);
    add(y, x);
  }
  dij();
  for (long long i = 2; i <= n; i++) {
    ans *= posi[i].size();
    if (ans >= k) break;
  }
  ans = min(ans, k);
  cout << ans << endl;
  memset(vis, 0, sizeof vis);
  dfs(2);
  return 0;
}
