#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > g[200005];
int dp[200005];
queue<int> q;
int n, m, k;
vector<string> ans;
string tmp = "";
void getAns(int u) {
  if (u == n + 1) {
    k--;
    ans.push_back(tmp);
    return;
  }
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i].first;
    int idx = g[u][i].second;
    if (dp[v] + 1 == dp[u]) {
      tmp[idx] = '1';
      getAns(u + 1);
      tmp[idx] = '0';
    }
    if (k == 0) return;
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    g[a].push_back(pair<int, int>(b, i));
    g[b].push_back(pair<int, int>(a, i));
    tmp += '0';
  }
  memset(dp, -1, sizeof(dp));
  q.push(1);
  dp[1] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < g[u].size(); i++) {
      int v = g[u][i].first;
      if (dp[v] == -1) dp[v] = dp[u] + 1, q.push(v);
    }
  }
  getAns(2);
  printf("%d\n", ans.size());
  for (int i = 0; i < ans.size(); i++) printf("%s\n", ans[i].c_str());
}
