#include <bits/stdc++.h>
inline int sbt(int x) { return __builtin_popcount(x); }
using namespace std;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
int n, m, k;
vector<pair<int, int> > adj[200005];
bool vis[200005];
int dis[200005];
vector<string> res;
string s;
void dfs(int node) {
  if (node > n) {
    res.push_back(s);
    return;
  }
  for (auto topr : adj[node]) {
    if (res.size() == k) return;
    int to = topr.first;
    if (dis[node] == (dis[to] + 1)) {
      s[topr.second] = '1';
      dfs(node + 1);
      s[topr.second] = '0';
    }
  }
}
int main() {
  cin.sync_with_stdio(false);
  cout.sync_with_stdio(false);
  fill(dis, dis + 200005, INT_MAX);
  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(make_pair(v, i));
    adj[v].push_back(make_pair(u, i));
  }
  queue<int> q;
  q.push(1);
  vis[1] = true;
  dis[1] = 0;
  while (!q.empty()) {
    int p = q.front();
    q.pop();
    for (auto nei : adj[p]) {
      if (!vis[nei.first]) {
        vis[nei.first] = true;
        q.push(nei.first);
        dis[nei.first] = dis[p] + 1;
      }
    }
  }
  for (int i = 0; i < m; i++) s += '0';
  dfs(2);
  cout << res.size() << endl;
  for (auto ele : res) cout << ele << endl;
  return 0;
}
