#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
vector<int> g[N];
vector<pair<int, int> > e[N];
vector<int> dis;
int n, m, k;
void get_dis(int s) {
  dis.resize(n, 1e9);
  dis[0] = 0;
  vector<int> vis(n, 0);
  queue<int> q;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (auto &v : e[u]) {
      if (dis[v.first] > dis[u] + 1) {
        dis[v.first] = dis[u] + 1;
        q.push(v.first);
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m >> k;
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    e[a].push_back(make_pair(b, i));
    e[b].push_back(make_pair(a, i));
  }
  get_dis(0);
  vector<vector<int> > a(n);
  for (int i = 0; i < n; ++i) {
    for (auto &v : e[i]) {
      if (dis[i] == dis[v.first] + 1) {
        a[i].push_back(v.second);
      }
    }
  }
  vector<int> c(n);
  int cnt = 0;
  int len = c.size();
  vector<string> ans;
  while (cnt < k) {
    string s(m, '0');
    for (int i = 1; i < n; ++i) {
      s[a[i][c[i]]] = '1';
    }
    ans.push_back(s);
    ++cnt;
    bool flag = 0;
    for (int i = 0; i < n; ++i) {
      if (c[i] + 1 < a[i].size()) {
        ++c[i];
        flag = 1;
        break;
      } else {
        c[i] = 0;
      }
    }
    if (!flag) break;
  }
  cout << ans.size() << endl;
  for (int i = 0; i < ans.size(); ++i) cout << ans[i] << endl;
  return 0;
}
