#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const int iinf = 1 << 29;
const long long llinf = 1ll << 60;
const double PI = 3.14159265;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long mrand(long long B) { return (unsigned long long)rng() % B; }
long long cross(pair<long long, long long> p1, pair<long long, long long> p2) {
  return p1.first * p2.second - p2.first * p1.second;
}
bool online(pair<long long, long long> a, pair<long long, long long> b,
            pair<long long, long long> c) {
  pair<long long, long long> p1{b.first - a.first, b.second - a.second};
  pair<long long, long long> p2{c.first - a.first, c.second - a.second};
  return cross(p1, p2) == 0;
}
void z_func(vector<int> &z, vector<int> &s, int n) {
  int L = 0, R = 0;
  for (int i = 1; i < n; i++) {
    if (i > R) {
      L = R = i;
      while (R < n && s[R - L] == s[R]) R++;
      z[i] = R - L;
      R--;
    } else {
      int k = i - L;
      if (z[k] < R - i + 1)
        z[i] = z[k];
      else {
        L = i;
        while (R < n && s[R - L] == s[R]) R++;
        z[i] = R - L;
        R--;
      }
    }
  }
}
int N, M, K;
int nprinted;
vector<vector<int>> answers;
vector<int> change;
void print_final() {
  cout << ((int)(answers).size()) << "\n";
  for (auto &a : answers) {
    for (auto &c : a) cout << c;
    cout << "\n";
  }
}
void print_all(vector<int> &cur, vector<vector<int>> &in_edges, int idx) {
  if (idx == ((int)(change).size())) {
    vector<int> tmp(M, 0);
    for (int i = 0; i < M; ++i) tmp[i] = cur[i];
    answers.push_back(tmp);
    ++nprinted;
    if (nprinted == K) {
      print_final();
      exit(0);
    }
    return;
  }
  int u = change[idx];
  for (int i = 0; i < ((int)(in_edges[u]).size()); ++i) {
    cur[in_edges[u][i]] = 1;
    print_all(cur, in_edges, idx + 1);
    cur[in_edges[u][i]] = 0;
  }
}
void work() {
  cin >> N >> M >> K;
  vector<pair<int, int>> edges(M);
  vector<vector<pair<int, int>>> g(N);
  for (int i = 0; i < M; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    g[u].push_back({v, i});
    g[v].push_back({u, i});
    edges[i] = {u, v};
  }
  int rem_k = K - 1;
  vector<int> dist(N, -1);
  vector<vector<int>> in_edges(N);
  queue<array<int, 3>> q;
  q.push({0, -1, 0});
  dist[0] = 0;
  while (!q.empty()) {
    array<int, 3> cur = q.front();
    q.pop();
    for (auto &p : g[cur[0]]) {
      if (dist[p.first] == -1) {
        dist[p.first] = cur[2] + 1;
        q.push({p.first, p.second, dist[p.first]});
        in_edges[p.first].push_back(p.second);
        continue;
      }
      if (dist[p.first] == cur[2] + 1 && rem_k) {
        --rem_k;
        in_edges[p.first].push_back(p.second);
      }
    }
  }
  for (int i = 1; i < N; ++i) {
    if (((int)(in_edges[i]).size()) > 1) change.push_back(i);
  }
  vector<int> ans1(M, 0);
  for (int i = 1; i < N; ++i) {
    assert(((int)(in_edges[i]).size()));
    ans1[in_edges[i][0]] = 1;
  }
  print_all(ans1, in_edges, 0);
  print_final();
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  work();
  return 0;
}
