#include <bits/stdc++.h>
using namespace std;
const int maxi = 1e6 + 2;
vector<int> v[maxi], pos[maxi];
int a[maxi], b[maxi], d[maxi], pred[maxi];
int n, m, k;
map<pair<int, int>, int> mp;
string s;
vector<string> ans;
void rek(int x) {
  if (!k) return;
  if (x == n + 1 && k) {
    s = "";
    for (int i = 1; i <= m; i++) s += '0';
    for (int i = 2; i <= n; i++) s[mp[{pred[i], i}]]++;
    ans.push_back(s);
    k--;
    return;
  }
  for (int i : pos[x]) {
    pred[x] = i;
    rek(x + 1);
  }
}
void bfs(int x) {
  for (int i = 1; i <= n; i++) d[i] = maxi;
  d[x] = 0;
  queue<int> q;
  q.push(x);
  while (!q.empty()) {
    int node = q.front();
    int val = d[node];
    q.pop();
    for (int i : v[node])
      if (d[i] == maxi) {
        d[i] = val + 1;
        q.push(i);
      }
  }
}
int main() {
  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &a[i], &b[i]);
    v[a[i]].push_back(b[i]);
    v[b[i]].push_back(a[i]);
    mp[{a[i], b[i]}] = i;
    mp[{b[i], a[i]}] = i;
  }
  bfs(1);
  for (int i = 1; i <= n; i++)
    for (int j : v[i])
      if (d[i] == d[j] + 1) pos[i].push_back(j);
  rek(2);
  cout << ans.size() << "\n";
  for (string s : ans) cout << s << endl;
  return 0;
}
