#include <bits/stdc++.h>
using namespace std;
char comp[200005];
vector<pair<int, int> > edge[200005];
vector<int> father[200005];
vector<string> ans;
int dis[200005], n, k;
queue<pair<int, int> > q;
void dfs(int u) {
  if (ans.size() >= k) return;
  if (u == n + 1) {
    ans.push_back(comp + 1);
    return;
  }
  for (int i = 0; i < father[u].size(); i++) {
    comp[father[u][i]] = '1';
    dfs(u + 1);
    comp[father[u][i]] = '0';
  }
}
int main() {
  char a[10];
  int m;
  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    edge[u].push_back(make_pair(v, i));
    edge[v].push_back(make_pair(u, i));
  }
  memset(dis, -1, sizeof(dis));
  for (int i = 1; i <= m; i++) comp[i] = '0';
  q.push(make_pair(1, 0));
  dis[1] = 0;
  while (!q.empty()) {
    pair<int, int> pa = q.front();
    q.pop();
    int u = pa.first, d = pa.second;
    for (int i = 0; i < edge[u].size(); i++) {
      int v = edge[u][i].first;
      if (dis[v] == -1) {
        dis[v] = d + 1;
        q.push(make_pair(v, d + 1));
      }
    }
  }
  for (int i = 2; i <= n; i++) {
    for (int j = 0; j < edge[i].size(); j++) {
      if (dis[i] == dis[edge[i][j].first] + 1)
        father[i].push_back(edge[i][j].second);
    }
  }
  dfs(2);
  if (ans.size() >= k) {
    cout << k << endl;
    for (int i = 0; i < k; i++) cout << ans[i] << endl;
  } else {
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); i++) cout << ans[i] << endl;
  }
  return 0;
}
