#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
struct Edge {
  int next, to, flag;
  Edge(int to = 0, int next = 0, int flag = 0) {
    this->next = next;
    this->to = to;
    this->flag = flag;
  }
} edge[maxn * 3];
int head[maxn], tot;
int dis[maxn];
vector<string> res;
int n, m, k;
vector<int> pre[maxn];
char s[maxn];
void addedge(int u, int v, int flag) {
  edge[tot].to = v;
  edge[tot].flag = flag;
  edge[tot].next = head[u];
  head[u] = tot++;
}
void bfs() {
  bool vis[maxn];
  memset(vis, 0, sizeof(vis));
  vis[1] = 1;
  dis[1] = 0;
  queue<pair<int, int> > op;
  op.push(pair<int, int>(1, 0));
  while (!op.empty()) {
    pair<int, int> u = op.front();
    op.pop();
    for (int i = head[u.first]; i != -1; i = edge[i].next) {
      int v = edge[i].to;
      if (!vis[v]) {
        dis[v] = u.second + 1;
        op.push(pair<int, int>(v, u.second + 1));
        vis[v] = 1;
      }
    }
  }
}
void dfs(int u) {
  if (res.size() >= k) return;
  if (u > n) {
    res.push_back(s + 1);
    return;
  }
  for (int i = 0; i < pre[u].size(); i++) {
    s[pre[u][i]] = '1';
    dfs(u + 1);
    s[pre[u][i]] = '0';
  }
}
int main() {
  ios::sync_with_stdio(false);
  memset(head, -1, sizeof(head));
  tot = 1;
  cin >> n >> m >> k;
  int u, v;
  for (int i = 0; i < m; i++) {
    cin >> u >> v;
    addedge(u, v, i + 1);
    addedge(v, u, i + 1);
  }
  bfs();
  for (int i = 2; i <= n; i++) {
    for (int j = head[i]; j != -1; j = edge[j].next) {
      if (dis[edge[j].to] + 1 == dis[i]) pre[i].push_back(edge[j].flag);
    }
  }
  for (int i = 1; i <= m; i++) s[i] = '0';
  dfs(2);
  cout << res.size() << endl;
  for (auto ans : res) {
    cout << ans << endl;
  }
  return 0;
}
