#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int dist[200002];
vector<pair<int, int>> v[200002];
vector<int> nes[200002];
char s[200002];
vector<string> ans;
void dfs(int d) {
  if (ans.size() >= k) return;
  if (d > n) {
    ans.push_back(s);
    return;
  }
  for (auto i : nes[d]) {
    s[i] = '1';
    dfs(d + 1);
    s[i] = '0';
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m >> k;
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    v[a].push_back({b, i});
    v[b].push_back({a, i});
  }
  queue<int> q;
  q.push(1);
  dist[1] = 1;
  while (q.size()) {
    int x = q.front();
    q.pop();
    for (auto i : v[x]) {
      if (dist[i.first]) continue;
      dist[i.first] = dist[x] + 1;
      q.push(i.first);
    }
  }
  for (int i = 2; i <= n; ++i) {
    for (auto j : v[i]) {
      if (dist[j.first] + 1 == dist[i]) nes[i].push_back(j.second);
    }
  }
  fill(s, s + m, '0');
  dfs(2);
  cout << ans.size() << '\n';
  for (auto i : ans) cout << i << '\n';
  return 0;
}
