#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, M = N << 1;
namespace Graph {
int h[N], ecnt, nxt[M], v[M], w[M];
void clear() { ecnt = 1; }
void add_dir(int _u, int _v, long long _w) {
  v[++ecnt] = _v;
  w[ecnt] = _w;
  nxt[ecnt] = h[_u];
  h[_u] = ecnt;
}
void add_undir(int _u, int _v, long long _w) {
  add_dir(_u, _v, _w);
  add_dir(_v, _u, _w);
}
}  // namespace Graph
using namespace Graph;
int n, m, k, id[N], dis[N];
queue<int> que;
bool vis[N];
void Bfs() {
  que.push(1);
  vis[1] = 1;
  dis[1] = 0;
  while (!que.empty()) {
    int u = que.front();
    que.pop();
    for (int i = h[u]; i; i = nxt[i])
      if (!vis[v[i]]) {
        vis[v[i]] = 1;
        dis[v[i]] = dis[u] + 1;
        que.push(v[i]);
      }
  }
}
bool cmp(int x, int y) { return dis[x] < dis[y]; }
int out[M];
void print() {
  if (!k) return;
  k--;
  for (int i = 1; i <= m; ++i) cout << out[i];
  cout << endl;
}
void get_tr(int uu) {
  if (uu > n) {
    print();
    return;
  }
  int u = id[uu];
  for (int i = h[u]; i; i = nxt[i])
    if (dis[v[i]] == dis[u] - 1) {
      out[w[i]] = 1;
      get_tr(uu + 1);
      out[w[i]] = 0;
      if (!k) return;
    }
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m >> k;
  clear();
  for (int i = 1; i <= m; ++i) {
    int x, y;
    cin >> x >> y;
    add_undir(x, y, i);
  }
  for (int i = 1; i <= n; ++i) id[i] = i;
  Bfs();
  long long tmp = 1;
  for (int u = 2; u <= n; ++u) {
    int now = 0;
    for (int i = h[u]; i; i = nxt[i])
      if (dis[v[i]] == dis[u] - 1) ++now;
    tmp *= now;
    if (tmp >= k) break;
  }
  if (tmp < k) k = tmp;
  sort(id + 1, id + n + 1, cmp);
  cout << k << endl;
  get_tr(2);
  return 0;
}
