#include <bits/stdc++.h>
using namespace std;

struct edges {
    int id, start, end;
    edges() {}
    edges(int i, int s, int e) : id(i), start(s), end(e) {}
};
struct edgesCmp {
    bool operator()(const edges &a, const edges &b) { return a.id < b.id; }
};

vector<edges> edgeList(2e5 + 10);
vector<vector<int>> graph(2e5 + 10);
vector<set<edges, edgesCmp>> validGraph(2e5 + 10);
vector<int> depth(2e5 + 10, -1);
vector<bool> visited(2e5 + 10, false);
vector<bool> edgeIsValid(2e5 + 10, false);
vector<bool> usedEdges(2e5 + 10, false);
int n, m, k, cnt = 0;

void bfs();
void dfs(int id, int visitedNum);

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; ++i) {
        int start, end;
        scanf("%d%d", &start, &end);
        edgeList.at(i) = edges(i, start, end);
        graph.at(start).push_back(end);
        graph.at(end).push_back(start);
    }
    bfs();
    dfs(1, 0);
}

void bfs() {
    queue<int> que;
    que.push(1);
    depth.at(1) = 0;
    while (!que.empty()) {
        int curPoint = que.front();
        que.pop();
        for (int end : graph.at(curPoint)) {
            if (depth.at(end) == -1) {
                depth.at(end) = depth.at(curPoint) + 1;
                que.push(end);
            }
        }
    }
    for (int i = 1; i <= m; ++i) {
        int start = edgeList.at(i).start, end = edgeList.at(i).end, id = edgeList.at(i).id;
        edgeIsValid.at(id) = true;
        if (depth.at(end) == depth.at(start) + 1) {
            validGraph.at(end).insert(edges(id, end, start));
            edgeList.at(id) = edges(id, start, end);
        } else if (depth.at(start) == depth.at(end) + 1) {
            validGraph.at(start).insert(edges(id, start, end));
            edgeList.at(id) = edges(id, end, start);
        } else {
            edgeIsValid.at(id) = false;
        }
        // cout << "depth(1):" << depth.at(1) << endl;
    }
    int num = 1;
    for (int i = 2; i <= n; ++i) {
        num *= validGraph.at(i).size();
        // cout << i << "\t" << depth.at(i) << "\t" << validGraph.at(i).size() << endl;
        if (num > k)
            break;
    }
    k = min(k, num);
    cout << k << endl;
}

void dfs(int id, int visitedNum) {
    if (cnt == k)
        return;
    if (id == m + 1) {
        // cout << "visitedNum:\t" << visitedNum << endl;
        /*for (int i = 1; i <= m; i++)
            cout << usedEdges[i] << "\t";
        cout << endl;*/
        if (visitedNum == m) {
            for (int i = 1; i <= m; i++) {
                if (usedEdges[i])
                    printf("%d", 1);
                else
                    printf("%d", 0);
            }
            printf("\n");
            cnt++;
        }
        return;
    }
    int start = edgeList.at(id).start, end = edgeList.at(id).end;
    int lastid = (*validGraph.at(end).end()--).id;

    if (!visited.at(end) && edgeIsValid.at(id)) {
        usedEdges.at(id) = true;
        visited.at(end) = true;
        dfs(id + 1, visitedNum + 1);
        usedEdges.at(id) = false;
        visited.at(end) = false;
    }

    if (id != lastid) {
        dfs(id + 1, visitedNum);
    }
}
/*
3 2 1000 1 2 1 3
*/

In file included from /usr/include/c++/8/map:60,
                 from /usr/include/x86_64-linux-gnu/c++/8/x32/bits/stdc++.h:81,
                 from /sandbox/1/a.cpp:1:
/usr/include/c++/8/bits/stl_tree.h: In instantiation of 'class std::_Rb_tree<edges, edges, std::_Identity<edges>, edgesCmp, std::allocator<edges> >':
/usr/include/c++/8/bits/stl_set.h:133:17:   required from 'class std::set<edges, edgesCmp>'
/sandbox/1/a.cpp:58:31:   required from here
/usr/include/c++/8/bits/stl_tree.h:457:21: error: static assertion failed: comparison object must be invocable as const
       static_assert(is_invocable_v<const _Compare&, const _Key&, const _Key&>,
                     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/sandbox/1/a.cpp: In function 'int main()':
/sandbox/1/a.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
/sandbox/1/a.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &start, &end);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~