CF1005F Berland and the Shortest Paths

题目描述

Berland 有 $n$ 座城市。一些城市通过道路连接。所有道路都是双向的。每条道路连接两个不同的城市。一对城市之间至多有一条道路。城市从 $1$ 到 $n$ 编号。

众所周知，从首都（编号为 $1$ 的城市），您可以沿着道路移动并到达任何其他城市。

Berland 的总统计划改善该国的道路网。预算足以修复 $n-1$ 道路。总统计划选择 $n-1$ 条道路，要求：

• 从首都出发沿着这 $n-1$ 条道路走可以到达其他所有的城市。
• 如果 $d_i$ 表示首都到 $i$ 号城市所需经过的路的条数，沿着选择的 n-1 条路走所得的 $d_1$+$d_2$+・・・+$d_n$ 应是最小的。

换句话说，这 $n-1$ 条道路的应该保持国家的连通性，并且使从城市 $1$ 到所有城市的距离的总和最小（你只能使用被选择的 $n-1$ 道路）。

总统命令有关部门准备 $k$ 个可能的选择，选择的 $n-1$ 条道路同时满足以上两个条件。

编写一个程序，找到 $k$ 种可能的方法来选择道路进行维修。如果少于 $k$ 种选法，则程序应输出所有可能的有效方式来选择道路。

输入格式

输入的第一行包含整数 $n,m,k.$ $(2 \leq$ $n \le$ $2 \cdot$ $10^5,$ $n-1$ $\leq$ $m \leq$ $2$ $\cdot$ $10^5,$ $1 \leq$ $k$ $\leq$ $2 \cdot$ $10^5$ $),$ $n$ 是这个国家的城市数，$m$ 是道路数，并且 $k$ 是选 $n-1$ 条道路修复的方案数。 数据保证 $m \cdot k \leq 10^6.$

接下来的 $m$ 行描述路的情况，每条路的描述占一行。每行包括两个整数 $a_i,b_i (1 \leq a_i,b_i\leq n,a_i \neq b_i)$—— 第 $i$ 条道路连接的两座城市的编号。一对城市最多有一条路连接。给定的路足以使你从首都出发到达任意城市。

输出格式

输出 $t (1 \leq t \leq k)$— 可选择的方案数量。记得你需要找到 $k$ 种不同的可行解，如果解的个数少于 $k$ 种，你需要输出所有可行解。

在接下来的 $t$ 行中，输出道路选择情况，一种一行。用 $m$ 个字符的字符串输出选择情况，其中，第 $j$ 个字符表示第 $j$ 条道路是否被选中，若是则用 $1$ 表示，若不是则用 $0$ 表示。路应该按照它们输入的顺序编号。各种选择情况的输出没有指定顺序。$t$ 行的所有输出应该不同。

因为题目保证 $m \cdot k\leq 10^6,t$ 行输出的总长不超过 $10^6.$

如果有很多组答案，任意输出它们中的一些即可。

输入输出样例 #1

输入 #1

4 4 3
1 2
2 3
1 4
4 3

输出 #1

2
1110
1011

输入输出样例 #2

输入 #2

4 6 3
1 2
2 3
1 4
4 3
2 4
1 3

输出 #2

1
101001

输入输出样例 #3

输入 #3

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

输出 #3

2
111100
110110