#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
int n, m, k, cnt = 1, ans = 1;
int head[N], dis[N];
char s[N];
vector<int> ve[N];
struct edge {
  int t, next;
} e[N << 1];
void add(int u, int t) {
  e[++cnt].t = t;
  e[cnt].next = head[u];
  head[u] = cnt;
}
queue<int> q;
void bfs(int x) {
  q.push(x);
  dis[x] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; i; i = e[i].next) {
      int t = e[i].t;
      if (dis[t]) continue;
      dis[t] = dis[u] + 1;
      q.push(t);
    }
  }
}
void dfs(int x) {
  if (!ans) return;
  if (x == n + 1) {
    puts(s + 1);
    ans--;
    return;
  }
  for (int i = 0; i < ve[x].size(); i++) {
    int k = ve[x][i];
    s[k] = '1';
    dfs(x + 1);
    s[k] = '0';
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1, u, v; i <= m; i++)
    scanf("%d%d", &u, &v), add(u, v), add(v, u);
  bfs(1);
  for (int i = 2; i <= n; i++) {
    cnt = 0;
    for (int j = head[i]; j; j = e[j].next) {
      if (dis[e[j].t] == dis[i] - 1) cnt++, ve[i].push_back(j / 2);
    }
    ans *= cnt;
    if (ans >= k) ans = k;
  }
  for (int i = 1; i <= m; i++) s[i] = '0';
  printf("%d\n", ans);
  dfs(2);
}
