#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define pii pair<int, int>

using namespace std;

const int N = 5e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = ;

int n, m, k, tot, d[N], head[N], ans[N];

LL cnt;

struct node {

    int u, v, nx;

} edge[N];

void add(int u, int v) {

    edge[tot].u = u;

    edge[tot].v = v;

    edge[tot].nx = head[u];

    head[u] = tot++;

}

vector<int> vec[N];

void bfs() {

    queue<int> que;

    d[] = ;

    que.push();

    while(!que.empty()) {

        int u = que.front(); que.pop();

        for(int i = head[u]; ~i; i = edge[i].nx) {

            int v = edge[i].v;

            if(d[v] != -) continue;

            d[v] = d[u] + ;

            que.push(v);

        }

    }

}

void dfs(int pos) {

    if(cnt <= ) return;

    if(pos == n + ) {

        cnt--;

        for(int i = ; i <= m; i++)

            printf("%d", ans[i]);

        puts("");

        return;

    }

    for(int i = ; i < vec[pos].size(); i++) {

        ans[vec[pos][i]] = ;

        dfs(pos + );

        ans[vec[pos][i]] = ;

    }

}

int main(){

    memset(head, -, sizeof(head));

    scanf("%d%d%d", &n, &m, &k);

    for(int i = ; i <= m; i++) {

        int u, v; scanf("%d%d", &u, &v);

        add(u, v);

        add(v, u);

    }

    memset(d, -, sizeof(d));

    bfs();

    for(int i = ; i < tot; i++) {

        int u = edge[i].u, v = edge[i].v;

        if(d[u] +  == d[v]) {

            vec[v].push_back(i /  + );

        }

    }

    cnt = ;

    for(int i = ; i <= n; i++) {

        cnt *= (int) vec[i].size();

        if(cnt >= k) break;

    }

    cnt = min(cnt, 1ll * k);

    printf("%lld\n", cnt);

    dfs();

    return ;

}

/*

*/