#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
int N, M, K;
vector<string> ans;
void f(int u, vector<vi> &cand, string &re, vi &U, vi &V) {
  if (u == N) {
    ans.push_back(re);
    return;
  }
  if ((int)(cand[u]).size() == 0) {
    f(u + 1, cand, re, U, V);
  }
  for (auto &(e) : (cand[u])) {
    int v = U[u] ^ V[v] ^ u;
    re[e] = '1';
    f(u + 1, cand, re, U, V);
    re[e] = '0';
    if ((int)(ans).size() == K) return;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20);
  cin >> N >> M >> K;
  vector<vi> G(N);
  vi U(M), V(M);
  for (int(i) = (0); (i) < (int)(M); ++(i)) {
    cin >> U[i] >> V[i];
    --U[i];
    --V[i];
    G[U[i]].push_back(i);
    G[V[i]].push_back(i);
  }
  vi D(N, INT_MAX / 2);
  D[0] = 0;
  queue<int> Q;
  Q.push(0);
  vector<vi> cand(N);
  vi vis(N);
  while ((int)(Q).size()) {
    int u = Q.front();
    Q.pop();
    for (auto &(e) : (G[u])) {
      int v = u ^ U[e] ^ V[e];
      if (D[u] + 1 <= D[v]) {
        if (D[u] + 1 < D[v]) Q.push(v);
        D[v] = D[u] + 1;
        cand[v].push_back(e);
      }
    }
  }
  string temp(M, '0');
  f(0, cand, temp, U, V);
  cout << (int)(ans).size() << endl;
  for (auto &(re) : (ans)) cout << re << endl;
}
