#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T& x) {
  char c;
  bool f = 0;
  while ((c = getchar()) < '0' || '9' < c) f |= (c == '-');
  for (x = (c ^ 48); '0' <= (c = getchar()) && c <= '9';
       x = (x << 1) + (x << 3) + (c ^ 48))
    ;
  if (f) x = -x;
}
template <class T>
inline T read(const T sample) {
  T x = 0;
  char c;
  bool f = 0;
  while ((c = getchar()) < '0' || '9' < c) f |= (c == '-');
  for (x = (c ^ 48); '0' <= (c = getchar()) && c <= '9';
       x = (x << 1) + (x << 3) + (c ^ 48))
    ;
  return f ? -x : x;
}
template <class T>
void fwrit(const T x) {
  if (x < 0) return (void)(putchar('-'), fwrit(-x));
  if (x > 9) fwrit(x / 10);
  putchar(x % 10 ^ 48);
}
template <class T>
inline T Max(const T x, const T y) {
  return x < y ? y : x;
}
template <class T>
inline T Min(const T x, const T y) {
  return x < y ? x : y;
}
template <class T>
inline T fab(const T x) {
  return x > 0 ? x : -x;
}
inline int gcd(const int a, const int b) { return b ? gcd(b, a % b) : a; }
inline void getInv(int inv[], const int lim, const int MOD) {
  inv[0] = inv[1] = 1;
  for (int i = 2; i <= lim; ++i)
    inv[i] = 1ll * inv[MOD % i] * (MOD - MOD / i) % MOD;
}
inline long long mulMod(const long long a, const long long b,
                        const long long mod) {
  return ((a * b - (long long)((long double)a / mod * b + 1e-8) * mod) % mod +
          mod) %
         mod;
}
const int maxn = 2e5;
const int maxm = 2e5;
struct edge {
  int to, nxt;
  edge(const int T = 0, const int N = 0) : to(T), nxt(N) {}
} e[maxm * 2 + 5];
int tail[maxn + 5], ecnt = 1;
inline void add_edge(const int u, const int v) {
  e[++ecnt] = edge(v, tail[u]);
  tail[u] = ecnt;
  e[++ecnt] = edge(u, tail[v]);
  tail[v] = ecnt;
}
vector<int> from[maxn + 5];
int n, m, k;
inline void Init() {
  n = read(1), m = read(1), k = read(1);
  int u, v;
  for (signed i = (1), i_end_ = (m); i <= i_end_; ++i) {
    u = read(1), v = read(1);
    add_edge(u, v);
  }
}
int layer[maxn + 5];
queue<int> Q;
inline void Bfs() {
  memset(layer, -1, sizeof layer);
  Q.push(1);
  layer[1] = 0;
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    for (signed i = tail[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to) {
      if (layer[v] == -1) {
        from[v].push_back(i >> 1);
        layer[v] = layer[u] + 1;
        Q.push(v);
      } else if (layer[u] + 1 == layer[v])
        from[v].push_back(i >> 1);
    }
  }
}
int cnt = 1;
inline void Get_cnt() {
  for (signed i = (2), i_end_ = (n); i <= i_end_; ++i) {
    cnt *= from[i].size();
    if (cnt >= k) {
      cnt = k;
      break;
    }
  }
}
bool choice[maxm + 5];
inline void Print() {
  --cnt;
  for (signed i = (1), i_end_ = (m); i <= i_end_; ++i)
    if (choice[i])
      putchar('1');
    else
      putchar('0');
  putchar('\n');
  if (cnt == 0) exit(0);
}
void Writans(const int now) {
  if (now == n + 1) {
    Print();
    return;
  }
  int sz = from[now].size();
  for (signed i = (0), i_end_ = (sz - 1); i <= i_end_; ++i) {
    choice[from[now][i]] = 1;
    Writans(now + 1);
    choice[from[now][i]] = 0;
  }
}
signed main() {
  Init();
  Bfs();
  Get_cnt();
  fwrit(cnt), putchar('\n');
  Writans(2);
  return 0;
}
