#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const double PI = acos(-1.0);
const long double eps = 1e-8;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 100;
const int N = 3e5 + 10;
const int M = 1e6 + 10;
const long long mm = (1LL << 32);
template <class T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool f = 0;
  for (; !isdigit(c); c = getchar()) f ^= c == '-';
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  x = f ? -x : x;
}
template <class T>
inline void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  T y = 1;
  int len = 1;
  for (; y <= x / 10; y *= 10) ++len;
  for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}
long long qpow(long long a, long long b, long long mod) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = (ans * a) % mod;
    b >>= 1;
    a = (a * a) % mod;
  }
  return ans;
}
int head[N], nxt[N << 2], to[N << 2], tot;
void add(int u, int v) {
  to[++tot] = v;
  nxt[tot] = head[u];
  head[u] = tot;
}
struct node {
  int dis, to;
  bool operator<(const node &b) const { return dis > b.dis; }
};
int dis[N];
void dij(int s) {
  priority_queue<node> q;
  memset(dis, inf, sizeof(dis));
  dis[s] = 0;
  q.push({dis[s], s});
  while (!q.empty()) {
    node Q = q.top();
    q.pop();
    int u = Q.to;
    if (Q.dis > dis[u]) continue;
    for (int i = head[u]; i; i = nxt[i]) {
      int v = to[i];
      if (dis[v] > dis[u] + 1) {
        dis[v] = dis[u] + 1;
        q.push({dis[v], v});
      }
    }
  }
}
int n, m, k;
int a[N], b[N];
vector<int> G[N];
vector<string> ans;
string t;
void dfs(int x) {
  if (ans.size() >= k) return;
  if (x == n + 1) {
    ans.push_back(t);
    return;
  }
  for (int v : G[x]) {
    t[v - 1] = '1';
    dfs(x + 1);
    t[v - 1] = '0';
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> k;
  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    add(u, v);
    add(v, u);
    a[i] = u, b[i] = v;
  }
  dij(1);
  for (int i = 1; i <= m; ++i) {
    int u = a[i], v = b[i];
    if (dis[u] + 1 == dis[v]) G[v].push_back(i);
    if (dis[v] + 1 == dis[u]) G[u].push_back(i);
  }
  for (int i = 0; i < m; ++i) t += '0';
  dfs(2);
  cout << ans.size() << endl;
  for (int i = 0; i < ans.size(); ++i) cout << ans[i] << endl;
  return 0;
}
