#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e5 + 9;
int n, m, k, dist[MAX], idx[MAX], cur[MAX];
vector<int> adj[MAX], can[MAX];
vector<pair<int, int> > edges;
bool vis[MAX];
void bfs() {
  queue<int> q;
  q.push(1);
  vis[1] = 1;
  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    for (int i = 0; i < adj[cur].size(); ++i) {
      int child = adj[cur][i];
      if (!vis[child]) {
        vis[child] = 1;
        dist[child] = dist[cur] + 1;
        q.push(child);
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m >> k;
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    adj[x].push_back(y);
    adj[y].push_back(x);
    edges.push_back({min(x, y), max(x, y)});
  }
  bfs();
  for (int i = 0; i < m; ++i) {
    int x = edges[i].first, y = edges[i].second;
    if (dist[x] + 1 == dist[y]) {
      can[y].push_back(i);
    }
    if (dist[y] + 1 == dist[x]) {
      can[x].push_back(i);
    }
  }
  vector<string> ans;
  for (int j = 0; j < k; ++j) {
    string add(m, '0');
    for (int i = 2; i <= n; ++i) {
      add[can[i][cur[i]]] = '1';
    }
    ans.push_back(add);
    bool is = 0;
    for (int i = 2; i <= n; ++i) {
      if (cur[i] + 1 < can[i].size()) {
        is = 1;
        ++cur[i];
        break;
      } else {
        cur[i] = 0;
      }
    }
    if (!is) {
      break;
    }
  }
  cout << ans.size() << "\n";
  for (int i = 0; i < ans.size(); ++i) {
    cout << ans[i] << "\n";
  }
  return 0;
}
