#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
vector<int> g[maxn];
map<pair<int, int>, int> m1;
queue<int> q1;
bool visit[maxn];
vector<int> ans[maxn];
vector<string> ans2;
string ans1;
int ind, k, n, m, cnt, dis[maxn];
void recur(int n1) {
  if (n1 == ind) {
    ans2.push_back(ans1);
    if (ans2.size() == k) {
      printf("%d\n", (int)ans2.size());
      for (int i = 0; i <= k - 1; i++) {
        cout << ans2[i] << endl;
      }
      exit(0);
    }
    return;
  }
  for (int i = 0; i <= (int)ans[n1].size() - 1; i++) {
    ans1[ans[n1][i] - 1] = '1';
    recur(n1 + 1);
    ans1[ans[n1][i] - 1] = '0';
  }
}
void solve() {
  scanf("%d", &n);
  scanf("%d", &m);
  scanf("%d", &k);
  ans1 = "";
  for (int i = 0; i <= m - 1; i++) {
    ans1 += "0";
  }
  for (int i = 1; i <= m; i++) {
    int n1, n2;
    scanf("%d", &n1);
    scanf("%d", &n2);
    g[n1].push_back(n2);
    g[n2].push_back(n1);
    m1[{n1, n2}] = i;
    m1[{n2, n1}] = i;
  }
  q1.push(1);
  visit[1] = 1;
  int i = 0;
  for (int i = 1; i <= n; i++) {
    dis[i] = maxn;
  }
  dis[1] = 0;
  while (!q1.empty()) {
    int element = q1.front();
    q1.pop();
    for (auto child : g[element]) {
      if (!visit[child]) {
        dis[child] = dis[element] + 1;
        visit[child] = 1;
        q1.push(child);
      }
    }
  }
  for (int child = 1; child <= n; child++) {
    for (auto par : g[child]) {
      if (dis[child] == dis[par] + 1) {
        ans[child - 1].push_back(m1[{child, par}]);
      }
    }
  }
  ind = n;
  recur(1);
  printf("%d\n", (int)ans2.size());
  for (int i = 0; i <= (int)ans2.size() - 1; i++) {
    cout << ans2[i] << endl;
  }
}
int main() {
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
