#include <bits/stdc++.h>
using namespace std;
vector<int> adjList[200000];
bool visited[200000];
vector<int> parents[200000];
vector<vector<bool> > edgeVector;
int n, m, k;
struct pair_hash {
  template <class T1, class T2>
  std::size_t operator()(const std::pair<T1, T2> &p) const {
    auto h1 = std::hash<T1>{}(p.first);
    auto h2 = std::hash<T2>{}(p.second);
    return h1 ^ h2;
  }
};
unordered_map<pair<int, int>, int, pair_hash> edgeMap;
void bfs(int start) {
  queue<int> myqueue;
  myqueue.push(start);
  myqueue.push(-1);
  unordered_set<int> nextLevelNodes;
  visited[start] = true;
  int count = 0;
  while (!myqueue.empty() && count < n) {
    int currNode = myqueue.front();
    myqueue.pop();
    if (currNode == -1) {
      nextLevelNodes.clear();
      myqueue.push(-1);
    } else {
      count++;
      for (int i = 0; i < adjList[currNode].size(); i++) {
        int node = adjList[currNode][i];
        if (visited[node]) {
          if (nextLevelNodes.find(node) != nextLevelNodes.end()) {
            parents[node].push_back(currNode);
          }
        } else {
          visited[node] = true;
          nextLevelNodes.insert(node);
          parents[node].push_back(currNode);
          myqueue.push(node);
        }
      }
    }
  }
}
void recursivePrint(int index, int &count, vector<bool> &edges) {
  for (int i = 0; i < parents[index].size(); i++) {
    if (count == k) return;
    int edge_a = index;
    int edge_b = parents[index][i];
    int edge_num;
    if (edge_a < edge_b)
      edge_num = edgeMap[{edge_a, edge_b}];
    else
      edge_num = edgeMap[{edge_b, edge_a}];
    edges[edge_num] = true;
    if (index == n - 1) {
      count++;
      edgeVector.push_back(edges);
    } else {
      recursivePrint(index + 1, count, edges);
    }
    edges[edge_num] = false;
  }
}
void printCases() {
  vector<bool> edges(m, false);
  int count = 0;
  recursivePrint(1, count, edges);
  cout << edgeVector.size() << endl;
  for (int i = 0; i < edgeVector.size(); i++) {
    for (int j = 0; j < m; j++) {
      cout << edgeVector[i][j];
    }
    cout << endl;
  }
}
int main() {
  cin >> n >> m >> k;
  for (int i = 0; i < n; i++) {
    adjList[i].clear();
    visited[i] = false;
    parents[i].clear();
  }
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    adjList[a].push_back(b);
    adjList[b].push_back(a);
    if (a < b)
      edgeMap.insert({{a, b}, i});
    else
      edgeMap.insert({{b, a}, i});
  }
  bfs(0);
  printCases();
}
