```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, m, k int
	fmt.Fscan(in, &n, &m, &k)

	type pair struct{ to, id int }
	adj := make([][]pair, n+1)
	for i := 0; i < m; i++ {
		var a, b int
		fmt.Fscan(in, &a, &b)
		adj[a] = append(adj[a], pair{b, i})
		adj[b] = append(adj[b], pair{a, i})
	}

	dist := make([]int, n+1)
	for i := range dist {
		dist[i] = -1
	}
	q := make([]int, 0, n)
	dist[1] = 0
	q = append(q, 1)
	for head := 0; head < len(q); head++ {
		u := q[head]
		for _, p := range adj[u] {
			v := p.to
			if dist[v] == -1 {
				dist[v] = dist[u] + 1
				q = append(q, v)
			}
		}
	}

	candidates := make([][]int, n+1)
	for v := 2; v <= n; v++ {
		for _, p := range adj[v] {
			u := p.to
			if dist[u] == dist[v]-1 {
				candidates[v] = append(candidates[v], p.id)
			}
		}
	}

	currIdx := make([]int, n+1)
	base := make([]byte, m)
	for i := range base {
		base[i] = '0'
	}

	results := make([]string, 0, k)

	for len(results) < k {
		s := make([]byte, m)
		copy(s, base)
		for v := 2; v <= n; v++ {
			s[candidates[v][currIdx[v]]] = '1'
		}
		results = append(results, string(s))

		v := n
		for v >= 2 && currIdx[v] == len(candidates[v])-1 {
			v--
		}
		if v < 2 {
			break
		}
		currIdx[v]++
		for u := v + 1; u <= n; u++ {
			currIdx[u] = 0
		}
	}

	fmt.Fprintln(out, len(results))
	for _, s := range results {
		out.WriteString(s)
		out.WriteByte('\n')
	}
}
```