#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
struct EDGE {
  int to, nxt, id;
} e[N << 1];
int head[N], tot;
int n, m, k;
int ans = 1;
int cnt;
int dis[N];
bool pd[N];
priority_queue<pair<int, int> > q;
bool vis[N];
vector<int> vec[N];
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 << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  return x * f;
}
void add(int x, int y, int id) {
  tot++;
  e[tot].to = y;
  e[tot].nxt = head[x];
  head[x] = tot;
  e[tot].id = id;
}
void Dij(int s) {
  memset(dis, 0x3f3f3f3f, sizeof(dis));
  memset(vis, 0, sizeof(vis));
  dis[s] = 0;
  q.push(make_pair(0, s));
  while (!q.empty()) {
    int x = q.top().second;
    q.pop();
    if (vis[x]) continue;
    vis[x] = true;
    for (int i = head[x]; i; i = e[i].nxt) {
      int y = e[i].to;
      if (dis[x] + 1 == dis[y]) vec[y].push_back(e[i].id);
      if (dis[x] + 1 < dis[y]) {
        vec[y].clear();
        vec[y].push_back(e[i].id);
        dis[y] = dis[x] + 1;
        q.push(make_pair(-dis[y], y));
      }
    }
  }
}
void DFS(int x) {
  if (x == n + 1) {
    cnt++;
    for (int i = 1; i <= m; i++) cout << pd[i];
    puts("");
    if (cnt == ans) exit(0);
  }
  for (int i = 0; i < vec[x].size(); i++) {
    pd[vec[x][i]] = 1;
    DFS(x + 1);
    pd[vec[x][i]] = 0;
  }
}
int main() {
  n = read(), m = read(), k = read();
  for (int i = 1; i <= m; i++) {
    int x = read(), y = read();
    add(x, y, i);
    add(y, x, i);
  }
  Dij(1);
  for (int i = 2; i <= n; i++) {
    if ((unsigned long long)ans * vec[i].size() > k) {
      ans = k;
      break;
    }
    ans *= vec[i].size();
  }
  cout << ans << endl;
  DFS(2);
  return 0;
}
