#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
string str = "";
int n, m, k, ans = 0;
vector<pair<int, int> > vec[200010];
vector<int> ids[200010];
vector<string> s;
int dist[200010];
bool check[200010];
void get_dist(int cur) {
  fill(dist, dist + 200010, INF);
  queue<int> q;
  q.push(cur);
  dist[cur] = 0;
  int tmp = 0;
  while (!q.empty()) {
    tmp = q.front();
    q.pop();
    for (int i = 0; i < vec[tmp].size(); i++) {
      int next = vec[tmp][i].first, num = vec[tmp][i].second;
      if (dist[next] > dist[tmp] + 1) {
        dist[next] = dist[tmp] + 1;
        q.push(next);
      }
      if (dist[next] == dist[tmp] + 1) {
        ids[next].push_back(num);
      }
    }
  }
  return;
}
void dfs(int cur) {
  if (cur == n + 1) {
    ans++;
    s.push_back(str);
    return;
  }
  for (int i = 0; i < ids[cur].size(); i++) {
    int num = ids[cur][i];
    str[num - 1] = '1';
    dfs(cur + 1);
    if (ans == k) return;
    str[num - 1] = '0';
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    vec[a].push_back(make_pair(b, i));
    vec[b].push_back(make_pair(a, i));
  }
  get_dist(1);
  for (int i = 0; i < m; i++) str += '0';
  dfs(2);
  cout << ans << "\n";
  for (int i = 0; i < s.size(); i++) cout << s[i] << "\n";
  return 0;
}
