#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
vector<pair<int, int> > edge;
vector<int> G[N];
vector<int> e[N];
int dis[N];
int n, m, k;
void init() {
  for (int i = 0; i < N; i++) G[i].clear(), e[i].clear();
  edge.clear();
}
void add_edge(int u, int v) {
  edge.push_back(make_pair(u, v));
  G[u].push_back(edge.size() - 1);
}
void bfs() {
  memset(dis, -1, sizeof(dis));
  dis[1] = 0;
  queue<int> q;
  q.push(1);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (auto id : G[u]) {
      auto ed = edge[id];
      int v = ed.second;
      if (dis[v] != -1) continue;
      dis[v] = dis[u] + 1;
      q.push(v);
    }
  }
}
void build_e() {
  for (int i = 1; i <= n; i++) {
    for (auto id : G[i]) {
      auto ed = edge[id];
      if (dis[ed.first] + 1 == dis[ed.second]) e[ed.second].push_back(id);
    }
  }
}
void dfs(int pos, vector<string>& ans, string& res) {
  if (ans.size() >= k) return;
  if (pos > n) {
    ans.push_back(res);
    return;
  }
  for (auto id : e[pos]) {
    res[id / 2] = '1';
    dfs(pos + 1, ans, res);
    res[id / 2] = '0';
  }
}
int main() {
  while (cin >> n >> m >> k) {
    init();
    for (int i = 0; i < m; i++) {
      int u, v;
      cin >> u >> v;
      add_edge(u, v);
      add_edge(v, u);
    }
    bfs();
    build_e();
    vector<string> ans;
    string res(m, '0');
    dfs(2, ans, res);
    cout << ans.size() << endl;
    for (auto ele : ans) cout << ele << endl;
  }
}
