#include <bits/stdc++.h>
using namespace std;
template <class U, class T>
void Max(U &first, T second) {
  if (first < second) first = second;
}
template <class U, class T>
void Min(U &first, T second) {
  if (first > second) first = second;
}
template <class T>
void add(int &a, T b) {
  a = (a + b) % 998244353;
}
int pow(int a, int b) {
  cerr << a << " " << b << "\n";
  int ans = 1;
  while (b) {
    if (b & 1) ans = 1LL * ans * a % 998244353;
    a = 1LL * a * a % 998244353;
    b >>= 1;
  }
  return ans;
}
int vis[200010], n, K, d[200010];
string s;
vector<string> ans;
vector<pair<int, int> > g[200010], e[200010];
void dfs(int u) {
  if (u == n) {
    ans.push_back(s);
    return;
  }
  for (auto &o : e[u]) {
    s[o.second] = '1';
    dfs(u + 1);
    if (int(ans.size()) == K) return;
    s[o.second] = '0';
  }
}
int main() {
  srand(time(NULL));
  int T, ca = 0, m = 0, k, i, j;
  scanf("%d%d%d", &n, &m, &K);
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &j, &k);
    j--, k--;
    g[j].push_back({k, i}), g[k].push_back({j, i});
  }
  queue<int> q;
  memset(d, -1, sizeof(d));
  q.push(0);
  d[0] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (auto &o : g[u]) {
      int v = o.first;
      if (d[v] == -1) {
        d[v] = d[u] + 1;
        q.push(v);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (auto &o : g[i]) {
      j = o.first;
      if (d[j] == d[i] - 1) {
        e[i].push_back({j, o.second});
      }
    }
  }
  for (int i = 0; i < m; i++) s += "0";
  dfs(1);
  printf("%d\n", int(ans.size()));
  for (auto &s : ans) puts(s.c_str());
}
