#include <bits/stdc++.h>
using namespace std;
const int NMAX = 200005;
vector<int> g[NMAX];
int d[NMAX], a[NMAX], b[NMAX];
vector<int> red[NMAX];
int main() {
  ios::sync_with_stdio(false);
  int n, m, k;
  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    cin >> a[i] >> b[i];
    g[a[i]].push_back(b[i]);
    g[b[i]].push_back(a[i]);
  }
  for (int i = 1; i <= n; i++) d[i] = INT_MAX;
  queue<int> q;
  q.push(1);
  d[1] = 0;
  while (q.size()) {
    int node = q.front();
    q.pop();
    for (auto it : g[node])
      if (d[it] == INT_MAX) {
        d[it] = 1 + d[node];
        q.push(it);
      }
  }
  for (int i = 1; i <= m; i++) {
    if (d[a[i]] == d[b[i]] + 1) red[a[i]].push_back(i);
    if (d[a[i]] + 1 == d[b[i]]) red[b[i]].push_back(i);
  }
  vector<int> f(n + 1, 0);
  vector<string> sol;
  for (int j = 1; j <= k; j++) {
    string s(m, '0');
    for (int i = 2; i <= n; i++) s[red[i][f[i]] - 1] = '1';
    sol.push_back(s);
    bool flag = 0;
    for (int i = 2; i <= n; i++) {
      if (f[i] + 1 < red[i].size()) {
        f[i]++;
        flag = 1;
        break;
      } else
        f[i] = 0;
    }
    if (!flag) break;
  }
  cout << sol.size() << "\n";
  for (auto it : sol) cout << it << "\n";
  return 0;
}
