#include <bits/stdc++.h>
using namespace std;
int n, m, k;
struct Edge {
  int from, to;
};
vector<Edge> edges;
vector<int> G[200005];
int dist[200005];
bool used[200005];
void addedge(int x, int y) {
  edges.push_back(Edge{x, y});
  edges.push_back(Edge{y, x});
  int m = edges.size();
  G[x].push_back(m - 2);
  G[y].push_back(m - 1);
}
void dijkstra() {
  for (int i = 1; i <= n; i++) {
    dist[i] = 999999999;
    used[i] = 0;
  }
  priority_queue<pair<int, int>, vector<pair<int, int> >,
                 greater<pair<int, int> > >
      pq;
  dist[1] = 0;
  pq.push(pair<int, int>(0, 1));
  while (!pq.empty()) {
    pair<int, int> now = pq.top();
    pq.pop();
    if (used[now.second]) continue;
    used[now.second] = 1;
    for (int i = 0; i < G[now.second].size(); i++) {
      int x = edges[G[now.second][i]].to;
      if (!used[x] && dist[x] > dist[now.second] + 1) {
        dist[x] = dist[now.second] + 1;
        pq.push(pair<int, int>(dist[x], x));
      }
    }
  }
}
vector<int> v[200005];
vector<vector<int> > ans;
vector<int> b;
bool book[200005];
void dfs(int now) {
  if (now == n + 1) {
    ans.push_back(b);
    return;
  }
  for (int i = 0; i < v[now].size(); i++) {
    b.push_back(v[now][i]);
    dfs(now + 1);
    b.pop_back();
    if (ans.size() == k) return;
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    addedge(x, y);
  }
  dijkstra();
  for (int i = 2; i <= n; i++) {
    for (int j = 0; j < G[i].size(); j++) {
      int now = edges[G[i][j]].to;
      if (dist[now] == dist[i] - 1) {
        v[i].push_back(G[i][j] / 2);
      }
    }
  }
  dfs(2);
  printf("%d\n", ans.size());
  for (int i = 0; i < ans.size(); i++) {
    for (int j = 0; j < m; j++) book[j] = 0;
    for (int j = 0; j < ans[i].size(); j++) book[ans[i][j]] = 1;
    for (int j = 0; j < m; j++) {
      if (book[j])
        printf("1");
      else
        printf("0");
    }
    printf("\n");
  }
  return 0;
}
