#include <bits/stdc++.h>
using namespace std;
const int MAX = 200000;
int n, m, k;
pair<int, int> edge[MAX];
int d[MAX];
vector<int> G[MAX];
void bfs() {
  queue<int> q;
  fill(d, d + n, MAX + 1);
  d[0] = 0;
  q.push(0);
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (auto w : G[v]) {
      if (d[v] + 1 < d[w]) {
        d[w] = d[v] + 1;
        q.push(w);
      }
    }
  }
}
vector<int> parent[MAX];
void print(int v, bool choice[], long long &options) {
  if (options == 0) return;
  if (v == n) {
    for (int i = 0; i < m; i++) {
      cout << (choice[i] ? 1 : 0);
    }
    cout << endl;
    options--;
    return;
  }
  for (auto e : parent[v]) {
    choice[e] = true;
    print(v + 1, choice, options);
    choice[e] = false;
  }
}
int main() {
  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    edge[i] = make_pair(a, b);
    G[a].push_back(b);
    G[b].push_back(a);
  }
  bfs();
  for (int i = 0; i < m; i++) {
    auto [a, b] = edge[i];
    if (d[a] + 1 == d[b]) {
      parent[b].push_back(i);
    }
    if (d[b] + 1 == d[a]) {
      parent[a].push_back(i);
    }
  }
  long long options = 1;
  for (int i = 1; i < n; i++) {
    options *= parent[i].size();
    if (options >= k) {
      options = k;
      break;
    }
  }
  cout << options << endl;
  bool choice[MAX] = {0};
  print(1, choice, options);
  return 0;
}
