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