#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int n, m, dis[maxn], k;
vector<pair<int, int> > edge[maxn];
vector<int> to1[maxn];
void add(int u, int v, int i) {
  edge[u].push_back(make_pair(v, i));
  edge[v].push_back(make_pair(u, i));
}
void bfs() {
  int i, j;
  for (i = 1; i <= n; i++) dis[i] = inf;
  dis[1] = 0;
  queue<int> qu;
  while (!qu.empty()) qu.pop();
  qu.push(1);
  while (!qu.empty()) {
    int u = qu.front();
    qu.pop();
    for (i = 0; i < edge[u].size(); i++) {
      int v = edge[u][i].first;
      if (dis[u] + 1 < dis[v]) {
        dis[v] = dis[u] + 1;
        qu.push(v);
      }
    }
  }
  return;
}
char res[maxn];
vector<string> ans;
void dfs(int u) {
  if (ans.size() > k) return;
  if (u == n + 1) {
    ans.push_back(res + 1);
    return;
  }
  for (int i = 0; i < to1[u].size(); i++) {
    int s = to1[u][i];
    res[s] = '1';
    dfs(u + 1);
    res[s] = '0';
  }
}
void solve() {
  int i, j, u, v;
  for (i = 1; i <= m; i++) {
    scanf("%d%d", &u, &v);
    add(u, v, i);
  }
  bfs();
  for (i = 2; i <= n; i++) {
    for (j = 0; j < edge[i].size(); j++) {
      int v = edge[i][j].first;
      if (dis[i] == dis[v] + 1) {
        to1[i].push_back(edge[i][j].second);
      }
    }
  }
  for (i = 1; i <= m; i++) res[i] = '0';
  dfs(2);
  int len = ans.size();
  len = min(len, k);
  printf("%d\n", len);
  for (i = 0; i < len; i++) {
    cout << ans[i] << endl;
  }
}
int main() {
  int i, j;
  scanf("%d%d%d", &n, &m, &k);
  solve();
  return 0;
}
