#include <bits/stdc++.h>
using namespace std;
template <typename T>
using maxHeap = priority_queue<T, vector<T>, less<T>>;
template <typename T>
using minHeap = priority_queue<T, vector<T>, greater<T>>;
template <typename Iter>
ostream& _out(ostream& s, Iter b, Iter e) {
  s << "[";
  for (auto it = b; it != e; it++) s << (it == b ? "" : " ") << *it;
  s << "]";
  return s;
}
template <typename A, typename B>
ostream& operator<<(ostream& s, const pair<A, B>& p) {
  return s << "(" << p.first << "," << p.second << ")";
}
template <typename T>
ostream& operator<<(ostream& s, const vector<T>& c) {
  return _out(s, begin(c), end(c));
}
bool debug = 0;
template <typename T>
void DEBUG(const T& x) {
  if (debug) cerr << x;
}
template <typename T, typename... Args>
void DEBUG(const T& head, const Args&... tail) {
  if (debug) {
    cerr << head;
    DEBUG(tail...);
  }
}
const int N = 200000 + 5;
const int INF = 1 << 30;
bool vis[N], used[N];
vector<pair<int, int>> G[N], egs;
vector<int> choice[N];
int dis[N], wh[N];
void dfs(int, int, int, int&);
int main(int argc, char* argv[]) {
  if (argc > 1 and string(argv[1]) == "-D") debug = 1;
  if (!debug) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  }
  int n, m, k;
  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    G[u].emplace_back(v, i);
    G[v].emplace_back(u, i);
    egs.emplace_back(u, v);
  }
  for (int i = 2; i <= n; i++) dis[i] = INF;
  queue<int> bfs;
  bfs.push(1);
  vis[1] = true;
  int step = 0;
  while (!bfs.empty()) {
    int u = bfs.front();
    bfs.pop();
    for (auto e : G[u]) {
      int v, id;
      tie(v, id) = e;
      if (dis[u] + 1 > dis[v])
        continue;
      else if (dis[u] + 1 < dis[v]) {
        dis[v] = dis[u] + 1;
        choice[step].push_back(id);
        wh[v] = step++;
        bfs.push(v);
      } else if (dis[u] + 1 == dis[v]) {
        choice[wh[v]].push_back(id);
      }
    }
  }
  int cnt = 1;
  for (int i = 0; i < step; i++) {
    cnt *= (int)((choice[i]).size());
    if (cnt > k) break;
  }
  cnt = min(cnt, k);
  cout << cnt << '\n';
  dfs(0, step, m, cnt);
  return 0;
}
void dfs(int id, int mx, int n, int& tot) {
  if (tot == 0) return;
  if (id == mx) {
    for (int i = 0; i < n; i++) cout << used[i];
    cout << '\n';
    tot--;
    return;
  }
  for (auto x : choice[id]) {
    used[x] = true;
    dfs(id + 1, mx, n, tot);
    used[x] = false;
    if (tot == 0) return;
  }
}
