#include <bits/stdc++.h>
using namespace std;
const long long MOD = (long long)(1e9 + 7);
long long modular(long long x) {
  x %= MOD;
  if (x < 0) x += MOD;
  return x;
}
const int MAXN = (int)(4e5 + 7);
int linhdeptrai[MAXN], d[MAXN], n, m, k, a[MAXN], b[MAXN];
vector<int> G[MAXN], I[MAXN];
vector<vector<char> > res;
vector<char> tmp;
void bfs() {
  queue<int> q;
  q.push(1);
  for (int i = 1; i <= n; i++) {
    linhdeptrai[i] = 1;
    d[i] = 0;
  }
  linhdeptrai[1] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (auto v : G[u]) {
      if (linhdeptrai[v]) {
        d[v] = d[u] + 1;
        linhdeptrai[v] = 0;
        q.push(v);
      }
    }
  }
}
void Try(int i) {
  if (k == 0) return;
  for (int j = 0; j < (int)I[i].size(); j++) {
    tmp[I[i][j] - 1] = '1';
    if (k == 0) return;
    if (i < n)
      Try(i + 1);
    else {
      if (k == 0) return;
      --k;
      res.push_back(tmp);
    }
    tmp[I[i][j] - 1] = '0';
    if (k == 0) return;
  }
}
int main() {
  while (~scanf("%d %d %d", &n, &m, &k)) {
    for (int i = 1; i <= n; i++) {
      G[i].clear();
      I[i].clear();
    }
    for (int i = 1; i <= m; i++) {
      scanf("%d %d", &a[i], &b[i]);
      G[a[i]].push_back(b[i]);
      G[b[i]].push_back(a[i]);
    }
    bfs();
    res.clear();
    tmp.clear();
    for (int i = 1; i <= m; i++) {
      tmp.push_back('0');
      if (d[a[i]] == d[b[i]] + 1) {
        I[a[i]].push_back(i);
      }
      if (d[b[i]] == d[a[i]] + 1) {
        I[b[i]].push_back(i);
      }
    }
    Try(2);
    cout << (int)res.size() << endl;
    for (int i = 0; i < (int)res.size(); i++) {
      for (int j = 0; j < m; j++) {
        cout << res[i][j];
      }
      cout << endl;
    }
  }
  return 0;
}
