#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
struct edge {
  int v, i;
};
int vis[N], d[N];
vector<edge> G[N], T[N];
vector<vector<int> > vec;
vector<int> P[N], nv;
queue<int> q;
int sz, n, m, k, cen, nxt[N * 10], from, mx;
void dfs(int i) {
  if (vec.size() - sz >= k) {
    return;
  }
  if (i < P[cen].size()) {
    for (edge e : T[P[cen][i]]) {
      nv.push_back(e.i);
      dfs(i + 1);
      nv.pop_back();
      if (vec.size() - sz >= k) {
        return;
      }
    }
  } else {
    nxt[vec.size()] = from;
    vec.push_back(nv);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> k;
  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});
  }
  q.push(0);
  P[1].push_back(0);
  vis[0] = 1;
  mx = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (edge e : G[u]) {
      if (vis[e.v] == 0) {
        vis[e.v] = vis[u] + 1;
        mx = max(mx, vis[e.v]);
        P[vis[e.v]].push_back(e.v);
        q.push(e.v);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (edge e : G[i]) {
      if (vis[e.v] + 1 == vis[i]) {
        T[i].push_back(e);
      }
    }
  }
  cen = 2;
  int l = 0;
  vec.push_back({});
  nxt[0] = -1;
  int sc = 0;
  while (1) {
    sz = vec.size();
    for (int i = l; i < sz; i++) {
      nv.clear();
      from = i;
      dfs(0);
      if (vec.size() - sz >= k) {
        break;
      }
    }
    l = sz;
    cen++;
    if (cen == mx + 1) break;
  }
  cout << vec.size() - l << endl;
  string s(m, '0');
  for (int i = l; i < vec.size(); i++) {
    int now = i;
    while (now != -1) {
      for (int j = 0; j < vec[now].size(); j++) {
        s[vec[now][j]] = '1';
      }
      now = nxt[now];
    }
    cout << s << endl;
    now = i;
    while (now != -1) {
      for (int j = 0; j < vec[now].size(); j++) {
        s[vec[now][j]] = '0';
      }
      now = nxt[now];
    }
  }
  return 0;
}
