#include <bits/stdc++.h>
using namespace std;
const int N = 2e5;
int n, m, k;
array<int, 2> e[N];
vector<int> adj[N];
bool vis[N];
int dis[N];
vector<int> inc[N];
void read() {
  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    cin >> e[i][0] >> e[i][1];
    e[i][0]--, e[i][1]--;
    adj[e[i][0]].push_back(e[i][1]);
    adj[e[i][1]].push_back(e[i][0]);
  }
}
void bfs() {
  dis[0] = 0;
  queue<int> q;
  q.push(0);
  vis[0] = true;
  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    for (auto i : adj[cur]) {
      if (!vis[i]) {
        q.push(i);
        vis[i] = true;
        dis[i] = dis[cur] + 1;
      }
    }
  }
}
void rededges() {
  for (int i = 0; i < m; i++) {
    int a = e[i][0], b = e[i][1];
    if (dis[a] + 1 == dis[b]) inc[b].push_back(i);
    if (dis[b] + 1 == dis[a]) inc[a].push_back(i);
  }
}
void solve() {
  bfs();
  rededges();
  vector<string> ans;
  vector<int> f(n);
  for (int i = 0; i < k; i++) {
    string s(m, '0');
    for (int i = 1; i < n; i++) {
      s[inc[i][f[i]]] = '1';
    }
    ans.push_back(s);
    bool ok = false;
    for (int i = 0; i < n; i++) {
      if (f[i] + 1 < inc[i].size()) {
        f[i]++;
        ok = true;
        break;
      } else
        f[i] = 0;
    }
    if (!ok) break;
  }
  cout << ans.size() << "\n";
  for (auto i : ans) cout << i << "\n";
}
int main() {
  int i = 0, j = 0, cs = 0, in;
  read();
  solve();
  return 0;
}
