#include <bits/stdc++.h>
using namespace std;
const long long N = 200001;
vector<vector<pair<long long, long long>>> g(N);
vector<vector<long long>> par(N);
vector<long long> edge(N, 0);
long long p = 0, r = 0, s = 0, h = 0;
void show(long long pos) {
  if (pos == s) {
    for (long long i = 0; i < par[pos].size(); ++i) {
      edge[par[pos][i]] = 1;
      for (long long j = 1; j <= h; ++j) cout << edge[j];
      cout << "\n";
      ++p;
      if (p == r) exit(0);
      edge[par[pos][i]] = 0;
    }
  } else {
    for (long long i = 0; i < par[pos].size(); ++i) {
      edge[par[pos][i]] = 1;
      show(pos + 1);
      edge[par[pos][i]] = 0;
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long n, m, k;
  cin >> n >> m >> k;
  for (long long i = 1; i <= m; ++i) {
    long long a, b;
    cin >> a >> b;
    g[a].push_back({b, i});
    g[b].push_back({a, i});
  }
  vector<long long> dist(n + 1, N);
  dist[1] = 0;
  queue<long long> q;
  q.push(1);
  while (q.size()) {
    long long v = q.front();
    q.pop();
    for (auto it : g[v]) {
      if (dist[it.first] > dist[v] + 1) {
        dist[it.first] = dist[v] + 1;
        par[it.first].push_back(it.second);
        q.push(it.first);
      } else if (dist[it.first] == dist[v] + 1)
        par[it.first].push_back(it.second);
    }
  }
  long long x = 1;
  for (long long i = 2; i <= n; ++i) {
    x *= (long long)(par[i].size());
    if (x > k) break;
  }
  r = min(x, k), s = n, h = m;
  cout << r << "\n";
  show(2);
}
