#include <bits/stdc++.h>
using namespace std;
const double g = 10.0, eps = 1e-12;
const int N = 200000 + 10, maxn = 1000 + 10, inf = 0x3f3f3f3f,
          INF = 0x3f3f3f3f3f3f3f3f;
vector<pair<int, int> > v[N];
vector<int> ans[N];
int dis[N], s[N];
void bfs() {
  queue<int> q;
  q.push(1);
  dis[1] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < v[u].size(); i++) {
      int x = v[u][i].first;
      if (!dis[x]) {
        dis[x] = dis[u] + 1;
        q.push(x);
      }
    }
  }
}
int n, m, k, cnt;
int a[N];
void dfs(int a[], int id) {
  if (k == 0) return;
  if (id == cnt + 1) {
    for (int i = 1; i <= cnt; i++) s[ans[i][a[i]]] = 1;
    k--;
    for (int i = 1; i <= m; i++) printf("%d", s[i]);
    puts("");
    for (int i = 1; i <= cnt; i++) s[ans[i][a[i]]] = 0;
  }
  if (k == 0) return;
  for (int i = 0; i < ans[id].size(); i++) {
    a[id] = i;
    dfs(a, id + 1);
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    v[a].push_back(make_pair(b, i)), v[b].push_back(make_pair(a, i));
  }
  bfs();
  int res = 1;
  for (int i = 2; i <= n; i++) {
    int co = 0;
    cnt++;
    for (int j = 0; j < v[i].size(); j++)
      if (dis[i] == dis[v[i][j].first] + 1)
        co++, ans[cnt].push_back(v[i][j].second);
    if (res < k) res *= co;
    if (co == 1) {
      s[ans[cnt][0]] = 1;
      ans[cnt].clear();
      cnt--;
    }
  }
  k = min(k, res);
  printf("%d\n", k);
  dfs(a, 1);
  return 0;
}
