#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int INF = 0x3f3f3f3f;
int n, m, k;
long long anstot = 1;
int Read() {
  int x = 0, f = 1;
  char c = getchar();
  while (c > '9' || c < '0') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x * 10) + (c ^ 48);
    c = getchar();
  }
  return x * f;
}
void Put1(int x) {
  if (x > 9) Put1(x / 10);
  putchar(x % 10 ^ 48);
}
void Put(int x, char c = -1) {
  if (x < 0) putchar('-'), x = -x;
  Put1(x);
  if (c >= 0) putchar(c);
}
template <typename T>
T Max(T x, T y) {
  return x > y ? x : y;
}
template <typename T>
T Min(T x, T y) {
  return x < y ? x : y;
}
template <typename T>
T Abs(T x) {
  return x < 0 ? -x : x;
}
int head[MAXN], tot = 1;
struct edge {
  int v, nxt;
} e[MAXN << 1];
void Add_Edge(int x, int y) {
  e[++tot].v = y;
  e[tot].nxt = head[x];
  head[x] = tot;
}
void Add_Double_Edge(int x, int y) {
  Add_Edge(x, y);
  Add_Edge(y, x);
}
int dis[MAXN];
vector<int> ans[MAXN];
void bfs() {
  for (int i = 2; i <= n; ++i) dis[i] = INF;
  queue<int> q;
  q.push(1);
  while (!q.empty()) {
    int t = q.front();
    q.pop();
    for (int i = head[t]; i; i = e[i].nxt)
      if (dis[t] + 1 <= dis[e[i].v]) {
        if (dis[t] + 1 < dis[e[i].v]) q.push(e[i].v);
        ans[e[i].v].push_back(i >> 1);
        dis[e[i].v] = dis[t] + 1;
      }
  }
}
bool vis[MAXN];
int dz[MAXN];
void dfs(int x) {
  if (x == n + 1) {
    anstot--;
    for (int i = 1; i <= m; ++i) Put(vis[i]);
    putchar('\n');
    if (!anstot) exit(0);
  }
  for (int i = 0, len = ans[x].size(); i < len; ++i)
    if (!vis[ans[x][i]])
      dz[x - 1] = ans[x][i], vis[ans[x][i]] = 1, dfs(x + 1), vis[ans[x][i]] = 0;
}
int main() {
  n = Read();
  m = Read();
  k = Read();
  for (int i = 1; i <= m; ++i) Add_Double_Edge(Read(), Read());
  bfs();
  for (int i = 2; i <= n && anstot < k; ++i) anstot = anstot * ans[i].size();
  anstot = Min(anstot, 1ll * k);
  Put(anstot, '\n');
  dfs(2);
  return 0;
}
