#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
int n, m, k, mxlvl, ans;
int a[maxn];
vector<pair<int, int> > e[maxn];
bool vis[maxn];
int q[maxn];
int dis[maxn];
vector<int> pre[maxn];
vector<int> level[maxn];
int fa[maxn];
char s[maxn];
void print(int a[], int n, int st = 0) {
  for (int i = 0; i < n; i++) {
    if (i != 0) printf(" ");
    printf("%d", a[i + st]);
  }
  printf("\n");
}
void init() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    e[u].push_back(make_pair(v, i));
    e[v].push_back(make_pair(u, i));
  }
}
void bfs(int root) {
  int st = 0, ed = 0;
  for (int i = 1; i <= n; i++) dis[i] = 1e8;
  q[st] = root;
  dis[root] = 0;
  vis[root] = true;
  mxlvl = 0;
  while (st <= ed) {
    int u = q[st++], d = dis[u];
    level[d].push_back(u);
    mxlvl = max(mxlvl, d);
    for (int i = 0; i < e[u].size(); i++) {
      int v = e[u][i].first;
      if (!vis[v]) {
        vis[v] = true;
        q[++ed] = v;
        dis[v] = d + 1;
      }
      if (dis[v] >= d + 1) pre[v].push_back(u);
    }
  }
}
void output() {
  for (int i = 0; i < m; i++) s[i] = '0';
  s[m] = 0;
  for (int i = 2; i <= n; i++) {
    for (int j = 0; j < e[i].size(); j++) {
      if (e[i][j].first == fa[i]) s[e[i][j].second] = '1';
    }
  }
  printf("%s\n", s);
}
void dfs_by_level(int lvl, int id) {
  if (lvl > mxlvl) {
    ans++;
    if (ans > k) exit(0);
    output();
    return;
  }
  int u = level[lvl][id];
  for (auto pa : pre[u]) {
    fa[u] = pa;
    if (id < level[lvl].size() - 1)
      dfs_by_level(lvl, id + 1);
    else
      dfs_by_level(lvl + 1, 0);
  }
}
void doit() {
  bfs(1);
  long long tot = 1;
  for (int i = 2; i <= n; i++) {
    tot *= pre[i].size();
    if (tot >= k) break;
  }
  if (tot >= k)
    printf("%d\n", k);
  else
    printf("%lld\n", tot);
  ans = 0;
  dfs_by_level(1, 0);
}
int main() {
  init();
  doit();
  return 0;
}
