#include <bits/stdc++.h>
using namespace std;
int n, m;
long long k;
vector<int> edge[300000];
vector<int> red[300000];
int dist[300000];
bool vis[300000];
bool vis2[300000];
long long l;
long long maxk = 1;
struct pii_hash {
  size_t operator()(const pair<int, int>& a) const {
    return 1000000000 * a.first + a.second;
  }
};
pair<int, int> indices[300000];
unordered_map<pair<int, int>, bool, pii_hash> used;
bool option[300000];
void readinput() {
  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    edge[a].push_back(b);
    edge[b].push_back(a);
    indices[i] = make_pair(a, b);
  }
}
void solve() {
  queue<pair<int, int> > q;
  q.push(make_pair(0, 0));
  while (!q.empty()) {
    int v = q.front().first;
    int d = q.front().second;
    q.pop();
    if (!vis[v]) {
      vis[v] = true;
      dist[v] = d;
      for (int i = 0; i < edge[v].size(); i++) {
        q.push(make_pair(edge[v][i], d + 1));
      }
    }
  }
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < edge[i].size(); j++) {
      if (dist[i] == dist[edge[i][j]] + 1) {
        red[i].push_back(edge[i][j]);
      }
    }
  }
}
void printoption() {
  for (int i = 0; i < m; i++) {
    if (!used.count(indices[i])) {
      cout << "0";
    } else {
      if (used[indices[i]]) {
        cout << "1";
      } else {
        cout << "0";
      }
    }
  }
  cout << endl;
}
void dfs(int node) {
  if (l == maxk || l == k) {
    return;
  }
  if (node == n - 1) {
    for (int i = 0; i < red[node].size(); i++) {
      l++;
      used[make_pair(node, red[node][i])] = true;
      used[make_pair(red[node][i], node)] = true;
      printoption();
      used[make_pair(node, red[node][i])] = false;
      used[make_pair(red[node][i], node)] = false;
      if (l == maxk || l == k) {
        return;
      }
    }
  } else {
    for (int i = 0; i < red[node].size(); i++) {
      used[make_pair(node, red[node][i])] = true;
      used[make_pair(red[node][i], node)] = true;
      dfs(node + 1);
      used[make_pair(node, red[node][i])] = false;
      used[make_pair(red[node][i], node)] = false;
    }
  }
}
void printoutput() {
  for (int i = 1; i < n; i++) {
    maxk = maxk * red[i].size();
    if (maxk >= k) {
      break;
    }
  }
  if (maxk >= k) {
    cout << k << endl;
  } else {
    cout << maxk << endl;
  }
  dfs(1);
}
int main() {
  readinput();
  solve();
  printoutput();
}
