#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fll;
vector<vector<int> > g;
vector<int> vis;
vector<int> lev;
int n, m, k;
vector<vector<int> > qual;
vector<vector<int> > com;
int qu = 0;
vector<int> quem;
void imprime() {
  for (int i = 0; i < m; i++) printf("%i", quem[i]);
  printf("\n");
  qu++;
}
void recur(int v) {
  if (v == n) {
    imprime();
    return;
  }
  for (int i = 0; i < com[v].size() && qu < k; i++) {
    quem[com[v][i]] = 1;
    recur(v + 1);
    quem[com[v][i]] = 0;
  }
}
int main(int argc, char const *argv[]) {
  scanf("%i %i %i", &n, &m, &k);
  g.resize(n);
  qual.resize(n);
  com.resize(n);
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%i %i", &a, &b);
    --a;
    --b;
    g[a].push_back(b);
    g[b].push_back(a);
    qual[a].push_back(i);
    qual[b].push_back(i);
  }
  vis.assign(n, 0);
  lev.assign(n, 0);
  queue<int> q;
  q.push(0);
  while (q.size()) {
    int v = q.front();
    q.pop();
    vis[v] = 1;
    for (int i = 0; i < g[v].size(); i++) {
      if (!vis[g[v][i]]) {
        lev[g[v][i]] = lev[v] + 1;
        vis[g[v][i]] = 1;
        q.push(g[v][i]);
      }
    }
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < g[i].size(); j++)
      if (lev[g[i][j]] == lev[i] + 1) {
        com[g[i][j]].push_back(qual[i][j]);
      }
  long long tam = 1;
  for (int i = 1; i < n && tam < k; i++) tam *= com[i].size();
  cout << min(tam, (long long)k) << endl;
  quem.assign(m, 0);
  recur(1);
  return 0;
}
