#include <bits/stdc++.h>
using namespace std;
int n, m, k;
vector<int> h[200001];
string result;
vector<string> results;
void getRes(int pos = 1) {
  if (pos == n) {
    results.push_back(result);
    return;
  }
  for (int v : h[pos]) {
    result[v] = '1';
    getRes(pos + 1);
    if (results.size() == k) return;
    result[v] = '0';
  }
}
signed main() {
  cin >> n >> m >> k;
  int a[m], b[m];
  vector<int> g[n];
  for (int i = 0; i < m; ++i) {
    cin >> a[i] >> b[i];
    a[i]--;
    b[i]--;
    g[a[i]].push_back(b[i]);
    g[b[i]].push_back(a[i]);
  }
  queue<int> q;
  vector<int> d(n, -1);
  q.push(0);
  d[0] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v : g[u])
      if (d[v] == -1) {
        d[v] = d[u] + 1;
        q.push(v);
      }
  }
  for (int i = 0; i < m; ++i)
    if (d[a[i]] + 1 == d[b[i]])
      h[b[i]].push_back(i);
    else if (d[b[i]] + 1 == d[a[i]])
      h[a[i]].push_back(i);
  result = string(m, '0');
  getRes();
  cout << results.size() << endl;
  for (string sss : results) cout << sss << endl;
  return 0;
}
