#1068. 1-08G. JM的最短路径问题

JM今天懒得编题面了，于是他直接把题意赤裸裸地甩了出来：

给定一个 $n$ 个点、 $m$ 条边的无向连通图，节点编号为 $1, 2, ..., n$ ，边的编号为 $1, 2, ..., m$ ，每条边的长度均为 $1$ 。

设 $dist(u,\ v)$ 表示图上从节点 $u$ 到节点 $v$ 的最短路径长度。要求在这 $m$ 条边中选择恰好 $n-1$ 条边，将其余边全部删除，使得 $sum = \sum_{i = 1}^{n}{dist(1,\ i)}$ 的值最小。

现在，你需要求出使得 $sum$ 最小的选边方案有多少种，并输出所有的合法方案。输出格式为 $b_1b_2...b_m$ ，其中 $b_i = 1/0$ 表示编号为 $i$ 的边选或不选。输出时按照01串 $b$ 的字典序从大到小输出。具体可参考输出样例。

当然，在某些情况下，合法的方案数可能会非常大。因此另外给定一个正整数 $k$ ，若合法的方案数超过 $k$ 种，则你需要输出的合法方案数为 $k$ ，并且接下来只输出字典序前 $k$ 大的 $k$ 种合法方案。

第一行三个正整数 $n,\ m,\ k$ ，其中 $n,\ m$ 分别表示图的点数和边数， $k$ 表示你需要输出的最大方案数。

接下来 $m$ 行，第 $i$ 行表示编号为 $i$ 的边，每行两个正整数 $u$ 和 $v$ ，表示这条双向边所连接的两个节点的编号。

输入保证图是连通的。

第一行一个正整数 $x$ ，表示使得 $sum$ 最小的选边方案有多少种。如果方案数超过 $k$ ，则输出 $k$ 而不是实际的方案数，也就是说你需要输出 $min(x,\ k)$ 。

接下来 $min(x,\ k)$ 行，每行一个01串 $b_1b_2...b_m$ ，表示一种合法的方案。输出时按照01串 $b$ 的字典序从大到小输出。若合法的方案数超过 $k$ 种，则只输出字典序前 $k$ 大的 $k$ 种合法方案。

样例输入1

3 2 1000
1 2
1 3

样例输出1

1
11

样例输入2

3 3 1000
1 2
2 3
3 1

样例输出2

1
101

样例输入3

5 6 1000
1 2
1 3
2 4
2 5
3 4
3 5

样例输出3

4
111100
111001
110110
110011

$2 \le n \le 2 \cdot 10^5$

$n-1 \le m \le 2 \cdot 10^5$

$1 \le k \le 2 \cdot 10^5$

$m \cdot k \le 10^6$

Hint

本题输出量较大，请使用scanf/printf以免I/O时间过长导致TLE。