#include <bits/stdc++.h>
using namespace std;
int n, m, k;
struct Edge {
  int a, b;
};
Edge edges[200010];
struct Node {
  std::vector<int> connectEdges;
  std::vector<int> connectNodes;
  int depth;
  std::vector<int> parentEdges;
  int pParentEdge;
};
Node nodes[200010];
char ansEdge[200010];
int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= n; i++) nodes[i].depth = -1;
  int temp;
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &(edges[i].a), &(edges[i].b));
    if (edges[i].a > edges[i].b) {
      temp = edges[i].b;
      edges[i].b = edges[i].a;
      edges[i].a = temp;
    }
    nodes[edges[i].a].connectEdges.push_back(i);
    nodes[edges[i].a].connectNodes.push_back(edges[i].b);
    nodes[edges[i].b].connectEdges.push_back(i);
    nodes[edges[i].b].connectNodes.push_back(edges[i].a);
  }
  nodes[1].depth = 0;
  int curP;
  std::queue<int> q;
  q.push(1);
  while (!q.empty()) {
    curP = q.front();
    q.pop();
    for (int i = 0; i < nodes[curP].connectNodes.size(); i++) {
      int p = nodes[curP].connectNodes[i];
      if (nodes[p].depth == -1) {
        nodes[p].parentEdges.clear();
        nodes[p].depth = nodes[curP].depth + 1;
        nodes[p].parentEdges.push_back(nodes[curP].connectEdges[i]);
        q.push(p);
      } else if (nodes[p].depth == (nodes[curP].depth + 1)) {
        nodes[p].parentEdges.push_back(nodes[curP].connectEdges[i]);
      }
    }
  }
  memset(ansEdge, 0, sizeof(ansEdge));
  for (int i = 0; i < m; i++) ansEdge[i] = '0';
  std::vector<int> nodesWithTwoMoreParents;
  nodesWithTwoMoreParents.clear();
  long long total = 1;
  for (int i = 1; i <= n; i++) {
    if (nodes[i].parentEdges.size() >= 2) {
      nodes[i].pParentEdge = 0;
      nodesWithTwoMoreParents.push_back(i);
      if (total < k) total = total * nodes[i].parentEdges.size();
      int p = nodes[i].parentEdges[0];
      ansEdge[p] = '1';
    } else if (nodes[i].parentEdges.size() == 1) {
      int p = nodes[i].parentEdges[0];
      ansEdge[p] = '1';
    }
  }
  if (total > k) total = k;
  printf("%d\n", total);
  for (int i = 0; i < total; i++) {
    printf("%s\n", ansEdge);
    int c = 1;
    for (int j = 0; j < nodesWithTwoMoreParents.size(); j++) {
      int p = nodesWithTwoMoreParents[j];
      ansEdge[nodes[p].parentEdges[nodes[p].pParentEdge]] = '0';
      nodes[p].pParentEdge = nodes[p].pParentEdge + c;
      if (nodes[p].pParentEdge >= nodes[p].parentEdges.size()) {
        nodes[p].pParentEdge = 0;
        ansEdge[nodes[p].parentEdges[nodes[p].pParentEdge]] = '1';
        c = 1;
      } else {
        ansEdge[nodes[p].parentEdges[nodes[p].pParentEdge]] = '1';
        break;
      }
    }
  }
  return 0;
}
