#include <bits/stdc++.h>
using namespace std;
template <typename T>
void out(T x) {
  cout << x << endl;
  exit(0);
}
using ll = long long;
const ll mod = 1e9 + 7;
const int maxn = 1e6 + 5;
int n, m, k;
vector<string> res;
string s;
vector<pair<int, int>> g[maxn];
int dist[maxn];
vector<int> par[maxn];
void dfs(int at) {
  if (at > n) {
    res.push_back(s);
    return;
  }
  for (int eid : par[at]) {
    s[eid] = '1';
    dfs(at + 1);
    s[eid] = '0';
    if (int(res.size()) >= k) return;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back({v, i});
    g[v].push_back({u, i});
  }
  memset(dist, -1, sizeof(dist));
  dist[1] = 0;
  queue<int> qq;
  qq.push(1);
  while (!qq.empty()) {
    int at = qq.front();
    qq.pop();
    for (auto ed : g[at]) {
      int to = ed.first;
      int id = ed.second;
      if (dist[to] == -1) {
        dist[to] = 1 + dist[at];
        qq.push(to);
      }
      if (dist[to] == 1 + dist[at]) {
        par[to].push_back(id);
      }
    }
  }
  s = string(m, '0');
  dfs(2);
  cout << res.size() << endl;
  for (auto x : res) {
    cout << x << "\n";
  }
  return 0;
}
