#include <bits/stdc++.h>
using namespace std;
int const N = 5e5 + 10, oo = 1e9;
int mod = oo + 7;
long long const OO = 1e18;
int n, m, k, w = 1, vis[N];
vector<int> adj[N], lv[N];
map<int, int> mp[N];
queue<int> q;
string an;
void BFS() {
  q.push(1);
  vis[1] = 1;
  int d = 2;
  while (!q.empty()) {
    int sz = q.size();
    while (sz--) {
      int cur = q.front();
      q.pop();
      if (vis[cur] != 1) {
        w *= lv[cur].size();
        w = min(w, k);
      }
      for (auto v : adj[cur]) {
        if (vis[v]) {
          if (vis[v] == d) lv[v].push_back(mp[cur][v]);
          continue;
        }
        lv[v].push_back(mp[cur][v]);
        q.push(v);
        vis[v] = d;
      }
    }
    d++;
  }
}
void rec(int u) {
  if (u > n) {
    cout << an << endl;
    w--;
    if (w == 0) exit(0);
    return;
  }
  for (auto e : lv[u]) {
    an[e] = '1';
    rec(u + 1);
    an[e] = '0';
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
    mp[a][b] = i;
    mp[b][a] = i;
  }
  BFS();
  cout << w << endl;
  for (int i = 0; i < m; i++) an += '0';
  rec(2);
  return 0;
}
