#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
struct node {
  int u, v;
  node(int x = 0, int y = 0) { u = x, v = y; }
} road[maxn];
bool vis[maxn];
int n, m, k, mindis, d[maxn], f[maxn];
vector<int> e[maxn], g[maxn];
void bfs() {
  queue<int> q;
  memset(vis, 0, sizeof(vis));
  memset(d, 0, sizeof(d));
  q.push(1);
  vis[1] = 1;
  while (!q.empty()) {
    int x = q.front();
    for (int i = 0; i < e[x].size(); i++) {
      int y = e[x][i];
      if (vis[y]) continue;
      vis[y] = 1;
      d[y] = d[x] + 1;
      q.push(y);
    }
    q.pop();
  }
  mindis = 0;
  for (int i = 1; i <= n; i++) mindis += d[i];
  return;
}
int main() {
  while (scanf("%d %d %d", &n, &m, &k) != EOF) {
    for (int i = 1; i <= n; i++) {
      e[i].clear();
      g[i].clear();
    }
    memset(f, 0, sizeof(f));
    int x, y;
    for (int i = 1; i <= m; i++) {
      scanf("%d %d", &x, &y);
      e[x].push_back(y);
      e[y].push_back(x);
      road[i] = node(x, y);
    }
    bfs();
    for (int i = 1; i <= m; i++) {
      x = road[i].u;
      y = road[i].v;
      if (d[x] + 1 == d[y]) g[y].push_back(i);
      if (d[y] + 1 == d[x]) g[x].push_back(i);
    }
    vector<string> ans;
    for (int i = 1; i <= k; i++) {
      string s(m + 1, '0');
      for (int j = 2; j <= n; j++) s[g[j][f[j]]] = '1';
      ans.push_back(string(s, 1, m));
      bool tag = false;
      for (int j = 2; j <= n; j++)
        if (f[j] + 1 < g[j].size()) {
          tag = true;
          f[j]++;
          break;
        } else
          f[j] = 0;
      if (!tag) break;
    }
    printf("%d\n", (int)ans.size());
    for (int i = 0; i < ans.size(); i++) cout << ans[i] << endl;
  }
  return 0;
}
