#include <bits/stdc++.h>
using namespace std;
int visit[310000];
vector<pair<int, int> > ed[310000];
vector<int> List[310000];
int n, m, k;
int print = 0;
string str;
void backTrack(int i) {
  if (print == k) exit(0);
  if (i == n + 1) {
    cout << str << "\n";
    print++;
    return;
  }
  for (auto v : List[i]) {
    str[v] = '1';
    backTrack(i + 1);
    str[v] = '0';
  }
}
int main() {
  memset(visit, 31, sizeof(visit));
  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    ed[u].push_back({v, i});
    ed[v].push_back({u, i});
  }
  queue<int> q;
  q.push(1);
  visit[1] = 0;
  while (q.empty() == false) {
    auto u = q.front();
    q.pop();
    for (auto v : ed[u]) {
      if (visit[u] + 1 == visit[v.first]) {
        List[v.first].push_back(v.second);
      } else if (visit[u] + 1 < visit[v.first]) {
        visit[v.first] = visit[u] + 1;
        List[v.first].push_back(v.second);
        q.push(v.first);
      }
    }
  }
  long long ans = 1;
  for (int i = 0; i < m; i++) str += '0';
  for (int i = 2; i <= n; i++) {
    ans *= List[i].size();
    if (ans > k) break;
  }
  k = min(ans, k + 0LL);
  cout << k << endl;
  backTrack(2);
  return 0;
}
