#include <bits/stdc++.h>
using namespace std;
vector<string> ans;
int n, m, K, d[200005];
queue<int> q;
char ch[200005];
int cnt, info[200005], nx[400005], v[400005], fan[400005];
void add(int u1, int v1, int k) {
  nx[++cnt] = info[u1];
  info[u1] = cnt;
  v[cnt] = v1;
  fan[cnt] = k;
}
void bfs() {
  d[1] = 1;
  q.push(1);
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = info[x]; i; i = nx[i])
      if (!d[v[i]]) d[v[i]] = d[x] + 1, q.push(v[i]);
  }
}
void dfs(int x) {
  if (ans.size() >= K) return;
  if (x == n + 1) {
    ans.push_back(ch + 1);
    return;
  }
  for (int i = info[x]; i; i = nx[i])
    if (d[v[i]] + 1 == d[x]) {
      ch[fan[i]] = '1';
      dfs(x + 1);
      ch[fan[i]] = '0';
    }
}
int main() {
  scanf("%d%d%d", &n, &m, &K);
  for (int i = 1, u1, v1; i <= m; i++)
    scanf("%d%d", &u1, &v1), add(u1, v1, i), add(v1, u1, i), ch[i] = '0';
  bfs();
  dfs(2);
  printf("%d\n", ans.size());
  for (int i = 0; i < ans.size(); puts(""), i++)
    for (int j = 0; j < m; j++) printf("%c", ans[i][j]);
}
