// 最短路径树 BFS 算法 O(N+M)
#include<bits/stdc++.h>
using namespace std;

const int N=2e5+5;
int idx,h[N],to[N<<1],ne[N<<1],id[N<<1];
void add(int a,int b,int c){
  to[++idx]=b;id[idx]=c;ne[idx]=h[a];h[a]=idx;
}
int n,m,k,sum,tot=1,d[N]; bool vis[N];
vector<int> pre[N];

void bfs(int s){
  queue<int> q;
  q.push(s); d[s]=0;
  while(!q.empty()){
    int u=q.front(); q.pop();
    for(int i=h[u];i;i=ne[i]){
      int v=to[i],w=id[i];
      if(!d[v]){
        d[v]=d[u]+1;
        pre[v].push_back(w); //保存v的前驱边编号
        q.push(v);
      }
      else if(d[v]==d[u]+1) pre[v].push_back(w);
    }
  }
}
void dfs(int x){ //输出tot种方案
  if(x==n+1){
    for(int i=1;i<=m;++i)printf("%d",vis[i]); //输出方案
    puts("");
    if(++sum==tot) exit(0);
    return;
  }
  for(int i=0;i<pre[x].size();++i){
    vis[pre[x][i]]=1; //选x的第i个前驱边
    dfs(x+1);         //枚举点2,3,4,...,n
    vis[pre[x][i]]=0; //不选
  }
}
signed main(){
  scanf("%d%d%d",&n,&m,&k);
  for(int i=1,x,y;i<=m;++i){
    scanf("%d%d",&x,&y);
    add(x,y,i),add(y,x,i);
  }
  
  bfs(1);
  for(int i=2;i<=n;++i){
    if(tot*pre[i].size()>k){tot=k;break;} 
    else tot*=pre[i].size();
  }
  printf("%d\n",tot); //方案数
  dfs(2);
}