#include <bits/stdc++.h>
using namespace std;
int m, k, dist[1000001], n;
vector<int> rodas[1000001];
vector<string> ans;
vector<pair<int, int> > g[1000001];
string s;
void f(int u) {
  if (u - 1 == n) return ans.push_back(s);
  for (size_t i = 0; i < rodas[u].size(); i++) {
    if ((int)ans.size() >= k) break;
    s[rodas[u][i] - 1] = '1';
    f(u + 1);
    s[rodas[u][i] - 1] = '0';
  }
}
int main() {
  cin.sync_with_stdio(0), cin.tie(0);
  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(pair<int, int>(v, i));
    g[v].push_back(pair<int, int>(u, i));
  }
  for (int i = 0; i < m; i++) s = s + '0';
  for (int i = 0; i <= n; i++) dist[i] = 1e9;
  queue<int> q;
  q.push(1);
  dist[1] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    int d = dist[u] + 1;
    for (auto v : g[u]) {
      if (d < dist[v.first]) {
        rodas[v.first].clear();
        dist[v.first] = d;
        rodas[v.first].push_back(v.second);
        q.push(v.first);
        continue;
      }
      if (d == dist[v.first]) rodas[v.first].push_back(v.second);
    }
  }
  f(2);
  cout << ans.size() << '\n';
  for (auto& v : ans) cout << v << '\n';
}
