#include <bits/stdc++.h>
using namespace std;
const int N = 200200;
int d[N];
vector<int> g[N];
vector<string> res;
int n, m, k;
map<pair<int, int>, int> mp;
int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    g[x].push_back(y);
    g[y].push_back(x);
    mp[make_pair(x, y)] = i;
    mp[make_pair(y, x)] = i;
  }
  for (int i = 0; i < n; i++) {
    d[i] = 1e9;
  }
  d[0] = 0;
  queue<int> q;
  q.push(0);
  while (q.size()) {
    int s = q.front();
    q.pop();
    for (int t : g[s]) {
      if (d[t] > d[s] + 1) {
        q.push(t);
        d[t] = d[s] + 1;
      }
    }
  }
  vector<vector<int>> par(n, vector<int>());
  for (int s = 0; s < n; s++) {
    for (int t : g[s]) {
      if (d[t] == d[s] + 1) {
        par[t].push_back(s);
      }
    }
  }
  string base = "";
  for (int i = 0; i < m; i++) {
    base += '0';
  }
  vector<int> aaa(n, 0);
  while (1) {
    if (res.size() == k) break;
    string s = base;
    for (int i = 1; i < n; i++) {
      s[mp[make_pair(i, par[i][aaa[i]])]] ^= 1;
    }
    res.push_back(s);
    bool change = false;
    for (int i = 1; i < n; i++) {
      if (aaa[i] == (int)(par[i].size()) - 1) {
        aaa[i] = 0;
      } else {
        change = true;
        aaa[i]++;
        break;
      }
    }
    if (!change) break;
  }
  cout << res.size() << "\n";
  for (string r : res) {
    cout << r << "\n";
  }
}
