#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5;
int n, m, k, tot, head[maxn], u, v, dis[maxn], cnt;
char s[maxn];
vector<string> ans;
struct edge {
  int to, next, id;
} e[maxn << 1];
void add_edge(int u, int v, int id) {
  e[++tot].to = v;
  e[tot].id = id;
  e[tot].next = head[u];
  head[u] = tot;
  return;
}
void dfs(int x) {
  if (x == n + 1) {
    ++cnt;
    ans.push_back(string(s + 1));
    return;
  }
  for (int i = head[x]; i; i = e[i].next) {
    if (dis[e[i].to] + 1 == dis[x]) {
      s[e[i].id] = '1';
      dfs(x + 1);
      s[e[i].id] = '0';
      if (cnt == k) break;
    }
  }
  return;
}
void bfs() {
  memset(dis, -1, sizeof(dis));
  queue<int> q;
  dis[1] = 0;
  q.push(1);
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = head[x]; i; i = e[i].next) {
      if (dis[e[i].to] == -1) {
        dis[e[i].to] = dis[x] + 1;
        q.push(e[i].to);
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m >> k;
  for (int i = 1; i <= m; ++i) {
    cin >> u >> v;
    add_edge(u, v, i);
    add_edge(v, u, i);
  }
  bfs();
  for (int i = 1; i <= m; ++i) {
    s[i] = '0';
  }
  dfs(2);
  cout << cnt << endl;
  for (int i = 0; i < cnt; ++i) {
    cout << ans[i] << endl;
  }
  return 0;
}
