#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
  if (a < b) swap(a, b);
  if (b == 0) return a;
  while ((a = a % b) != 0) {
    swap(a, b);
  }
  return b;
}
long long mpow(long long x, long long y, long long m) {
  long long res = 1;
  while (y > 0) {
    if (y & 1) res = res * x % m;
    y = y >> 1;
    x = x * x % m;
  }
  return res;
}
long long ncr(long long n, long long r) {
  if (r > n) return 0;
  long long res = 1;
  for (long long i = (1); i < (r + 1); i++) res = res * (n - r + i) / i;
  return res;
}
long long *sieve(long long n) {
  long long *lpf = new long long[n + 1];
  for (long long i = 1; i <= n; i++) lpf[i] = i;
  long long rt = (long long)floor(sqrt(n)) + 1;
  for (long long i = (2); i < (rt); i++) {
    if (lpf[i] != i) continue;
    for (long long j = i * i; j <= n; j += i) {
      if (lpf[j] == j) lpf[j] = i;
    }
  }
  return lpf;
}
void solve() {
  long long n, m, k, u, v;
  cin >> n >> m >> k;
  vector<pair<long long, long long> > adj[n];
  for (long long i = (0); i < (m); i++) {
    cin >> u >> v;
    u--, v--;
    adj[u].push_back(make_pair(v, i));
    adj[v].push_back(make_pair(u, i));
  }
  pair<long long, long long> dis[n];
  for (long long i = (0); i < (n); i++) dis[i] = make_pair(-1, i);
  queue<long long> q;
  dis[0].first = 0;
  q.push(0);
  while (!q.empty()) {
    long long x = q.front();
    q.pop();
    for (pair<long long, long long> y : adj[x]) {
      if (dis[y.first].first != -1) continue;
      dis[y.first].first = dis[x].first + 1;
      q.push(y.first);
    }
  }
  vector<long long> prev[n];
  long long pt[n];
  memset(pt, 0, sizeof(pt));
  for (long long i = (0); i < (n); i++) {
    for (pair<long long, long long> y : adj[i]) {
      if (dis[y.first].first < dis[i].first) prev[i].push_back(y.second);
    }
  }
  vector<string> ans;
  string s;
  for (long long i = (0); i < (m); i++) s.push_back('0');
  for (long long i = (1); i < (n); i++) {
    s[prev[i][0]] = '1';
  }
  ans.push_back(s);
  while (ans.size() != k) {
    bool flag = 0;
    for (long long i = (n - 1); i > (-1); i--) {
      if (i == 0) {
        flag = 1;
        break;
      }
      s[prev[i][pt[i]]] = '0';
      pt[i]++;
      if (pt[i] == prev[i].size()) pt[i] = 0;
      s[prev[i][pt[i]]] = '1';
      if (pt[i] != 0) break;
    }
    if (flag) break;
    ans.push_back(s);
  }
  cout << ans.size() << "\n";
  for (string t : ans) cout << t << "\n";
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long t = 1;
  for (long long i = (1); i < (t + 1); i++) {
    solve();
    cout << "\n";
  }
}
