#include <bits/stdc++.h>
using namespace std;
const int NN = 202200;
vector<int> adj[NN], pa[NN], ans;
int deep[NN], print[NN];
int n, m, k, cnt = 1;
map<pair<int, int>, int> mp;
void bfs(int u) {
  memset(deep, 0x3f, sizeof deep);
  deep[u] = 0;
  queue<int> q;
  q.push(u);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v : adj[u]) {
      if (deep[v] > deep[u] + 1) {
        deep[v] = deep[u] + 1;
        q.push(v);
      }
    }
  }
}
void dfs(int u) {
  if (u == n + 1) {
    for (int i = 1; i <= m; i++) print[i] = 0;
    for (int uu : ans) {
      print[uu] = 1;
    }
    for (int i = 1; i <= m; i++) printf("%d", print[i]);
    puts("");
    cnt--;
    if (!cnt) exit(0);
    return;
  }
  for (int v : pa[u]) {
    ans.push_back(mp[{u, v}]);
    dfs(u + 1);
    ans.pop_back();
  }
}
int main() {
  scanf("%d %d %d", &n, &m, &k);
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    adj[u].push_back(v);
    adj[v].push_back(u);
    mp[{u, v}] = mp[{v, u}] = i;
  }
  bfs(1);
  for (int i = 1; i <= n; i++) {
    for (int j : adj[i]) {
      if (deep[j] + 1 == deep[i]) pa[i].push_back(j);
    }
  }
  for (int i = 1; i <= n; i++) {
    if (!pa[i].empty()) cnt = cnt * pa[i].size();
    if (cnt >= k) break;
  }
  cnt = min(cnt, k);
  cout << cnt << endl;
  dfs(2);
  return 0;
}
