#include <bits/stdc++.h>
using namespace std;
int n, e, k;
vector<vector<int> > g;
vector<vector<int> > E;
vector<int> p[200000];
int cost[200000];
void BFS() {
  queue<int> q;
  q.push(0);
  memset(cost, -1, sizeof(cost));
  cost[0] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    int idx = 0;
    for (auto &v : g[u]) {
      if (cost[v] == -1 || cost[v] == cost[u] + 1) {
        if (cost[v] == -1) q.push(v);
        cost[v] = cost[u] + 1;
        p[v].push_back(E[u][idx]);
      }
      ++idx;
    }
  }
}
vector<string> sol;
string cur;
void print(int i) {
  if (sol.size() == k) return;
  if (i == 0) {
    sol.push_back(cur);
    return;
  }
  for (int j = 0; j < p[i].size(); ++j) {
    cur[p[i][j]] = '1';
    print(i - 1);
    if (sol.size() == k) return;
    cur[p[i][j]] = '0';
  }
}
int main() {
  scanf("%d%d%d", &n, &e, &k);
  g.resize(n);
  E.resize(n);
  for (int i = 0, a, b; i < e; ++i) {
    scanf("%d%d", &a, &b);
    --a;
    --b;
    g[a].push_back(b);
    g[b].push_back(a);
    E[a].push_back(i);
    E[b].push_back(i);
  }
  BFS();
  cur.resize(e, '0');
  print(n - 1);
  printf("%d\n", sol.size());
  for (auto &e : sol) printf("%s\n", e.c_str());
  return 0;
}
