#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
vector<int> G[maxn], S[maxn];
void insert(int u, int v) {
  G[u].push_back(v);
  G[v].push_back(u);
}
int dist[maxn];
int u[maxn], v[maxn];
int n, m, k;
int vis[maxn];
queue<int> q;
void bfs() {
  q.push(1);
  memset(dist, 0x3f, sizeof dist);
  dist[1] = 0;
  vis[1] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v : G[u])
      if (!vis[v]) {
        dist[v] = dist[u] + 1;
        q.push(v);
        vis[v] = 1;
      }
  }
}
int ans[maxn];
void dfs(int p) {
  if (!k) return;
  if (p > n) {
    for (int i = 1; i <= m; i++) printf("%d", ans[i]);
    puts("");
    --k;
    return;
  }
  for (int x : S[p]) {
    ans[x] = 1;
    dfs(p + 1);
    ans[x] = 0;
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", u + i, v + i);
    insert(u[i], v[i]);
  }
  bfs();
  for (int i = 1; i <= m; i++) {
    if (dist[u[i]] + 1 == dist[v[i]]) S[v[i]].push_back(i);
    if (dist[v[i]] + 1 == dist[u[i]]) S[u[i]].push_back(i);
  }
  long long ans = 1;
  for (int i = 2; i <= n && ans < k; i++) ans *= S[i].size();
  printf("%lld\n", min(ans, 1ll * k));
  dfs(2);
  return 0;
}
