#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * f;
}
int n, m, t;
int u[N], v[N];
struct node {
  int to, last;
} tree[N * 2];
int s = 0, head[N];
inline void add(int from, int to) {
  tree[++s].to = to;
  tree[s].last = head[from];
  head[from] = s;
}
int deep[N];
deque<int> q;
inline void prework() {
  q.push_back(1);
  deep[1] = 1;
  while (q.size()) {
    int now = q.front();
    q.pop_front();
    for (int i = head[now]; i; i = tree[i].last) {
      int k = tree[i].to;
      if (deep[k]) continue;
      deep[k] = deep[now] + 1;
      q.push_back(k);
    }
  }
}
vector<int> mp[N];
int flag[N];
int cnt = 0;
inline void dfs(int place) {
  if (place == n + 1) {
    cnt++;
    for (int i = 1; i <= m; i++) printf("%d", flag[i]);
    printf("\n");
    return;
  }
  for (int i = 0; i < mp[place].size(); i++) {
    flag[mp[place][i]] = true;
    dfs(place + 1);
    flag[mp[place][i]] = false;
    if (cnt == t) return;
  }
}
int main() {
  n = read();
  m = read();
  t = read();
  for (int i = 1; i <= m; i++) {
    u[i] = read();
    v[i] = read();
    add(u[i], v[i]);
    add(v[i], u[i]);
  }
  prework();
  for (int i = 1; i <= m; i++)
    if (deep[u[i]] > deep[v[i]]) swap(u[i], v[i]);
  for (int i = 1; i <= m; i++)
    if (deep[v[i]] == deep[u[i]] + 1) mp[v[i]].push_back(i);
  int ans = 1, now = t;
  for (int i = 2; i <= n; i++) {
    int siz = mp[i].size();
    if (!siz) {
      ans = 0;
      break;
    }
    now /= siz;
    if (!now) {
      ans = t;
      break;
    }
    ans *= siz;
  }
  printf("%d\n", ans);
  if (!ans) return 0;
  dfs(2);
  return 0;
}
