#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
vector<int> V[N], G[N];
queue<int> Q;
int sp[N];
map<pair<int, int>, int> ID;
char ans[N];
int t, n;
void dfs(int No) {
  if (No > n) {
    cout << ans << '\n';
    t--;
    return;
  }
  for (auto k : G[No]) {
    pair<int, int> p = {k, No};
    int u = ID[p];
    ans[u] = '1';
    dfs(No + 1);
    if (t <= 0) return;
    ans[u] = '0';
  }
}
int main() {
  int m, k;
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    V[u].push_back(v);
    V[v].push_back(u);
    pair<int, int> a = {u, v}, b = {v, u};
    ID[a] = ID[b] = i;
    ans[i] = '0';
  }
  fill(sp, sp + N, INF);
  sp[1] = 0;
  Q.push(1);
  while (!Q.empty()) {
    int p = Q.front();
    Q.pop();
    for (auto k : V[p]) {
      if (sp[k] == INF) {
        sp[k] = sp[p] + 1;
        Q.push(k);
        G[k].push_back(p);
      } else if (sp[k] == sp[p] + 1)
        G[k].push_back(p);
    }
  }
  long long out = 1;
  for (int i = 2; i <= n; i++) {
    out *= G[i].size();
    if (out > k) break;
  }
  t = min(out, (long long)k);
  cout << t << '\n';
  dfs(2);
}
