#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<int> > g(n);
  vector<int> a(m), b(m);
  for (int i = 0; i < m; ++i) {
    cin >> a[i] >> b[i];
    a[i]--;
    b[i]--;
    g[a[i]].push_back(b[i]);
    g[b[i]].push_back(a[i]);
  }
  const int INF = 1e9;
  queue<int> q;
  q.push(0);
  vector<int> d(n, INF);
  d[0] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v : g[u])
      if (d[v] == INF) {
        d[v] = d[u] + 1;
        q.push(v);
      }
  }
  vector<vector<int> > inc(n);
  for (int i = 0; i < m; ++i)
    if (d[a[i]] + 1 == d[b[i]])
      inc[b[i]].push_back(i);
    else if (d[a[i]] == d[b[i]] + 1)
      inc[a[i]].push_back(i);
  vector<int> f(n);
  vector<string> res;
  for (int i = 0; i < k; ++i) {
    string ans(m, '0');
    for (int l = 1; l < n; ++l) ans[inc[l][f[l]]] = '1';
    res.push_back(ans);
    bool go = false;
    for (int l = 1; l < n; ++l)
      if (f[l] + 1 < inc[l].size()) {
        f[l]++;
        go = true;
        break;
      } else
        f[l] = 0;
    if (!go) break;
  }
  cout << res.size() << '\n';
  for (auto elem : res) cout << elem << '\n';
}
