#include <bits/stdc++.h>
using namespace std;
struct arista {
  int desde, hasta, id;
};
vector<vector<arista> > ady;
int n, m, k;
vector<vector<int> > usadas;
void BFS(int inicio) {
  vector<int> dist(n + 1, (1 << 29));
  queue<int> cola;
  dist[inicio] = 0;
  cola.push(inicio);
  while (cola.size()) {
    int nodo = cola.front();
    cola.pop();
    for (int i = 0; i < ady[nodo].size(); i++) {
      int vecino = ady[nodo][i].hasta;
      int idArista = ady[nodo][i].id;
      if (dist[nodo] + 1 < dist[vecino]) {
        dist[vecino] = dist[nodo] + 1;
        usadas[vecino] = vector<int>(1, idArista);
        cola.push(vecino);
      } else if (dist[nodo] + 1 == dist[vecino]) {
        usadas[vecino].push_back(idArista);
      }
    }
  }
}
vector<vector<bool> > pos;
void recursion(vector<bool> &b, int nodo) {
  if (nodo == n + 1) {
    pos.push_back(b);
    return;
  }
  if (pos.size() >= k) return;
  for (int i = 0; i < usadas[nodo].size(); i++) {
    b[usadas[nodo][i]] = 1;
    recursion(b, nodo + 1);
    b[usadas[nodo][i]] = 0;
  }
}
int main() {
  cin >> n >> m >> k;
  ady.resize(n + 1);
  usadas.resize(n + 1);
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    ady[a].push_back({a, b, i});
    ady[b].push_back({b, a, i});
  }
  BFS(1);
  vector<bool> b(m, false);
  recursion(b, 2);
  cout << min(k, (int)pos.size()) << endl;
  for (int i = 0; i < min(k, (int)pos.size()); i++) {
    for (int j = 0; j < m; j++) {
      cout << pos[i][j];
    }
    cout << endl;
  }
  return 0;
}
