#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e5 + 10;
const int MOD = 998244353;
const double PI = acos(-1.0);
vector<pair<int, int> > e[MAX];
vector<int> ans[MAX];
vector<string> s;
string str;
int v[MAX];
int n, tot;
void bfs() {
  queue<int> p;
  for (int i = 0; i < e[1].size(); i++) {
    pair<int, int> nex = e[1][i];
    p.push(nex.first);
    v[nex.first] = 1;
  }
  while (!p.empty()) {
    int k = p.front();
    p.pop();
    for (int i = 0; i < e[k].size(); i++) {
      pair<int, int> nex = e[k][i];
      if (nex.first == 1 || (v[nex.first] >= 1 && v[nex.first] <= v[k]))
        continue;
      if (v[nex.first] == 0) {
        v[nex.first] = v[k] + 1;
        ans[nex.first].push_back(nex.second);
        p.push(nex.first);
      } else if (v[nex.first] == v[k] + 1)
        ans[nex.first].push_back(nex.second);
    }
  }
}
void dfs(int k) {
  if (k == n + 1 && s.size() < tot) {
    s.push_back(str);
    return;
  }
  if (v[k]) dfs(k + 1);
  for (int i = 0; i < ans[k].size(); i++) {
    if (s.size() == tot) return;
    int nex = ans[k][i];
    str[nex - 1] = '1';
    dfs(k + 1);
    str[nex - 1] = '0';
  }
}
int main() {
  int m;
  cin >> n >> m >> tot;
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    e[x].push_back({y, i});
    e[y].push_back({x, i});
  }
  bfs();
  memset(v, 0, sizeof v);
  v[1] = 1;
  str = "";
  for (int i = 0; i < m; i++) str += '0';
  for (int i = 0; i < e[1].size(); i++) {
    pair<int, int> nex = e[1][i];
    str[nex.second - 1] = '1';
    v[nex.first] = 1;
  }
  dfs(1);
  cout << s.size() << endl;
  for (int i = 0; i < s.size(); i++) cout << s[i] << endl;
  return 0;
}
