#include <bits/stdc++.h>
using namespace std;
const long long int INF = 1LL << 60;
long long int n, m, k, x, y, z;
int mod = 1e9 + 7;
long long int add(long long int a, long long int b) {
  if (a + b >= mod) return a + b - mod;
  return a + b;
}
long long int sub(long long int a, long long int b) {
  if (a < b) return a - b + mod;
  return a - b;
}
long long int mul(long long int a, long long int b) {
  return 1LL * a * b % mod;
}
int power(int a, int b) {
  if (b < 0) return 0;
  int re = 1;
  while (b) {
    if (b & 1) {
      re = mul(re, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return re;
}
bool sortbysec(const pair<long long int, long long int> &a,
               const pair<long long int, long long int> &b) {
  return (a.second < b.second);
}
bool sortbyfi(
    const pair<long long int, pair<long long int, long long int>> &a,
    const pair<long long int, pair<long long int, long long int>> &b) {
  return (a.first > b.first);
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>
    pq;
long long int bs(vector<long long int> v, long long int x) {
  long long int hi = v.size() - 1, lo = 0;
  while (hi >= lo) {
    long long int mid = lo + (hi - lo) / 2;
    if (v[mid] == x)
      return 1;
    else if (v[mid] < x)
      lo = mid + 1;
    else
      hi = mid - 1;
  }
  return 0;
}
bool paired(char a, char b) {
  if (a == '[' and b == ']') return true;
  if (a == '{' and b == '}') return true;
  if (a == '(' and b == ')') return true;
  if (a == '<' and b == '>') return true;
  return false;
}
bool cmp(pair<long long int, vector<long long int>> a,
         pair<long long int, vector<long long int>> b) {
  return a.first > b.first;
}
long long int dp[200005] = {0};
void update1(long long int idx, long long int val) {
  while (idx <= 100000) {
    dp[idx] = max(dp[idx], val);
    idx += idx & -idx;
  }
}
long long int pref1(long long int idx) {
  long long int ans = 0;
  while (idx > 0) {
    ans = max(dp[idx], ans);
    idx -= idx & -idx;
  }
  return ans;
}
long long int bit[200005] = {0};
void update(long long int idx, long long int val) {
  while (idx <= 100000) {
    bit[idx] += val;
    idx += idx & -idx;
  }
}
long long int pref(long long int idx) {
  long long int ans = 0;
  while (idx > 0) {
    ans += bit[idx];
    idx -= idx & -idx;
  }
  return ans;
}
long long int rsum(long long int l, long long int r) {
  return pref(r) - pref(l - 1);
}
vector<long long int> g[2 * 200005], option[2 * 200005];
vector<long long int> vis(2 * 200005), d(2 * 200005);
string s = "";
void bfs(long long int u) {
  for (int i = 0; i < (200001); ++i) d[i] = INF, vis[i] = 0;
  d[u] = 0;
  vis[u] = 1;
  queue<long long int> q;
  q.push(u);
  while (!q.empty()) {
    u = q.front();
    q.pop();
    for (auto v : g[u]) {
      if (!vis[v]) {
        vis[v] = true;
        d[v] = d[u] + 1;
        q.push(v);
      }
    }
  }
}
vector<string> ans;
void f(long long int pos) {
  if (pos == n + 1) {
    ans.push_back(s);
    if ((int)ans.size() == k) {
      cout << ans.size() << "\n";
      for (auto i : ans) cout << i << "\n";
      exit(0);
    }
  }
  for (auto i : option[pos]) {
    s[i] = '1';
    f(pos + 1);
    s[i] = '0';
  }
}
void Birdperson() {
  cin >> n >> m >> k;
  map<std::pair<long long int, long long int>, long long int> mp;
  for (int i = 0; i < (m); ++i) {
    s += "0";
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
    mp[{x, y}] = i;
    mp[{y, x}] = i;
  }
  bfs(1);
  for (long long int i = 2; i <= n; i++) {
    for (auto v : g[i]) {
      if (d[i] == d[v] + 1) option[i].push_back(mp[{i, v}]);
    }
  }
  f(2);
  cout << ans.size() << "\n";
  for (auto i : ans) cout << i << "\n";
}
int main() {
  std::ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long int t = 1;
  long long int cnt = 1;
  while (cnt <= t) {
    Birdperson();
    cnt++;
  }
  return 0;
}
