#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> v[200010];
int d[200010];
bool vis[200010];
vector<pair<int, int>> fa[200010];
vector<vector<int>> res;
vector<int> tmp;
int n, m, k;
int cnt;
void solve(int deep) {
  if (cnt == k) return;
  if (deep == n + 1) {
    res.push_back(tmp);
    cnt++;
    return;
  }
  for (auto it : fa[deep]) {
    tmp.push_back(it.second);
    solve(deep + 1);
    tmp.pop_back();
  }
}
int main() {
  scanf("%d %d %d", &n, &m, &k);
  for (int i = 1; i <= m; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    v[a].push_back({b, i});
    v[b].push_back({a, i});
  }
  memset(d, -1, sizeof(d));
  d[1] = 0;
  queue<int> q;
  q.push(1);
  while (q.size()) {
    int x = q.front();
    q.pop();
    if (vis[x]) continue;
    vis[x] = true;
    for (auto it : v[x]) {
      if (d[it.first] != -1 && d[it.first] + 1 == d[x]) {
        fa[x].push_back(it);
      } else if (d[it.first] == -1) {
        q.push(it.first);
        d[it.first] = d[x] + 1;
      }
    }
  }
  solve(2);
  printf("%d\n", (int)res.size());
  for (auto it : res) {
    sort(it.begin(), it.end());
    auto p = it.begin();
    for (int i = 1; i <= m; i++) {
      if (p != it.end() && (*p) == i) {
        putchar('1');
        p++;
      } else {
        putchar('0');
      }
    }
    printf("\n");
  }
  return 0;
}
